Home

Hello, my name is Iñaki Garay. I'm a programmer from Argentina. This is where I put some of my stuff, notes, bits and pieces from around the internet that are important to me, etc. If you find something that's yours and you don't want it here, reach out to me: igarai at gmail.

Mathematics

Bayesian

• Github: Bayesian Data Analysis Course
• Probabilistic Programming & Bayesian Methods for Hackers
• Jupyter Notebook: Probabilistic Programming and Bayesian Methods for Hackers
• Thomas Bayes and the crisis in science
• 2014/03/11 Frequentism and Bayesianism: A Practical Introduction
• 2019/02/20 An Overview of Bayesian Inference

Algorithms

AI

Table of Contents

• Agents
• Expert Systems
• Game AI
• Machine Learning
  • Deep Learning
  • Capsule Networks
  • Neural Networks
• Natural Language Processing

Agents

• AgentBase Agent Based Modeling (ABM) in the browser
• Babel The all-in-one toolkit for multi-agent experiments on emergent communication
• OpenAgent An agent library for systems of nested automata.
• JALSE
• LessWrong: Complex Behavior from Simple (Sub)Agents

Expert Systems

• CLIPS A Tool for Building Expert Systems
• Tutorialspoint: Artificial Intelligence - Expert Systems

Game AI

Machine Learning

Deep Learning

Capsule Networks

Neural Networks

Natural Language Processing

Artificial Intelligence Timeline

• Sources:
  • http://en.wikipedia.org/wiki/Timeline_of_artificial_intelligence
  • http://biology.kenyon.edu/slonc/bio3/AI/TIMELINE/timeline.html

Belief-Desires-Intentions Model

Table of Contents

• Book
• Notes
  • Wikipedia
  • Bratman
    • Beliefs
    • Beliefset
    • Desires
    • Goals
    • Intentions
    • Plans
    • Events
    • BDI Interpreter
    • Limitations and Criticisms

Book

• Prologue
  • Multiagent Systems and Distributed Artificial Intelligence
    • Intelligent Agents that Interact
    • Challenging Issues
    • Applications
    • Rationales for Multiagent Systems
  • A Guide to This Book
    • The Chapters
    • The Exercises
    • A Few Pointers to Further Readings
    • References
• Part I: Basic Themes
  • 1 Intelligent Agents
    • 1.1 Introduction
    • 1.2 What Are Agents?
      • 1.2.1 Examples of Agents
      • 1.2.2 Intelligent Agents
      • 1.2.3 Agents and Objects
      • 1.2.4 Agents and Expert Systems
    • 1.3 Abstract Architectures for Intelligent Agents
      • 1.3.1 Purely Reactive Agents
      • 1.3.2 Perception
      • 1.3.3 Agents with State
    • 1.4 Concrete Architectures for Intelligent Agents
      • 1.4.1 Logic-based Architectures
      • 1.4.2 Reactive Architectures
      • 1.4.3 Belief-Desire-Intention Architectures
      • 1.4.4 Layered Architectures
    • 1.5 Agent Programming Languages
      • 1.5.1 Agent-Oriented Programming
      • 1.5.2 Concurrent METATEM
    • 1.6 Conclusions
    • 1.7 Exercises
    • 1.8 References
  • 2 Multiagent Systems and Societies of Agents
    • 2.1 Introduction
      • 2.1.1 Motivations
      • 2.1.2 Characteristics of Multiagent Environments
    • 2.2 Agent Communications
      • 2.2.1 Coordination
      • 2.2.2 Dimensions of Meaning
      • 2.2.3 Message Types
      • 2.2.4 Communication Levels
      • 2.2.5 Speech Acts
      • 2.2.6 Knowledge Query and Manipulation Language (KQML)
      • 2.2.7 Knowledge Interchange Format (KIF)
      • 2.2.8 Ontologies
      • 2.2.9 Other Communication Protocols
    • 2.3 Agent Interaction Protocols
      • 2.3.1 Coordination Protocols
      • 2.3.2 Cooperation Protocols
      • 2.3.3 Contract Net
      • 2.3.4 Blackboard Systems
      • 2.3.5 Negotiation
      • 2.3.6 Multiagent Belief Maintenance
      • 2.3.7 Market Mechanisms
    • 2.4 Societies of Agents
    • 2.5 Conclusions
    • 2.6 Exercises
    • 2.7 References
  • 3 Distributed Problem Solving and Planning
    • 3.1 Introduction
    • 3.2 Example Problems
    • 3.3 Task Sharing
      • 3.3.1 Task Sharing in the Tower of Hanoi (Toll) Problem
      • 3.3.2 Task Sharing in Heterogeneous Systems
      • 3.3.3 Task Sharing for Distributed Sensor Network Establishment (DSNE)
      • 3.3.4 Task Sharing for Interdependent Tasks
    • 3.4 Result Sharing
      • 3.4.1 Functionally Accurate Cooperation
      • 3.4.2 Shared Repositories and Negotiated Search
      • 3.4.3 Distributed Constrained Heuristic Search
      • 3.4.4 Organizational Structuring
      • 3.4.5 Communication Strategies
      • 3.4.6 Task Structures
    • 3.5 Distributed Planning
      • 3.5.1 Centralized Planning for Distributed Plans
      • 3.5.2 Distributed Planning for Centralized Plans
      • 3.5.3 Distributed Planning for Distributed Plans
    • 3.6 Distributed Plan Representations
    • 3.7 Distributed Planning and Execution
      • 3.7.1 Post-Planning Coordination
      • 3.7.2 Pre-Planning Coordination
      • 3.7.3 Interleaved Planning, Coordination, and Execution
      • 3.7.4 Runtime Plan Coordination Without Communication
    • 3.8 Conclusions
    • 3.9 Exercises
    • 3.10 References
  • 4 Search Algorithms for Agents
    • 4.1 Introduction
    • 4.2 Constraint Satisfaction
      • 4.2.1 Definition of a Constraint Satisfaction Problem
      • 4.2.2 Filtering Algorithm
      • 4.2.3 Hyper-Resolution-Based Consistency Algorithm
      • 4.2.4 Asynchronous Backtracking
      • 4.2.5 Asynchronous Weak-Commitment Search
    • 4.3 Path-Finding Problem
      • 4.3.1 Definition of a Path-Finding Problem
      • 4.3.2 Asynchronous Dynamic Programming
      • 4.3.3 Learning Real-Time A*
      • 4.3.4 Real-Time A*
      • 4.3.5 Moving Target Search
      • 4.3.6 Real-Time Bidirectional Search
      • 4.3.7 Real-Time Multiagent Search
    • 4.4 Two-Player Games
      • 4.4.1 Formalization of Two-Player Games
      • 4.4.2 Minimax Procedure
      • 4.4.3 Alpha-Beta Pruning
    • 4.5 Conclusions
    • 4.6 Exercises
    • 4.7 References
  • 5 Distributed Rational Decision Making
    • 5.1 Introduction
    • 5.2 Evaluation Criteria
      • 5.2.1 Social Welfare
      • 5.2.2 Pareto Efficiency
      • 5.2.3 Individual Rationality
      • 5.2.4 Stability
      • 5.2.5 Computational Efficiency
      • 5.2.6 Distribution and Communication Efficiency
    • 5.3 Voting
      • 5.3.1 Truthful Voters
      • 5.3.2 Strategic (Insincere) Voters
    • 5.4 Auctions
      • 5.4.1 Auction Settings
      • 5.4.2 Auction Protocols
      • 5.4.3 Efficiency of the Resulting Allocation
      • 5.4.4 Revenue Equivalence and Non-Equivalence
      • 5.4.5 Bidder Collusion
      • 5.4.6 Lying Auctioneer
      • 5.4.7 Bidders Lying in Non-Private-Value Auctions
      • 5.4.8 Undesirable Private Information Revelation
      • 5.4.9 Roles of Computation in Auctions
    • 5.5 Bargaining
      • 5.5.1 Axiomatic Bargaining Theory
      • 5.5.2 Strategic Bargaining Theory
      • 5.5.3 Computation in Bargaining
    • 5.6 General Equilibrium Market Mechanisms
      • 5.6.1 Properties of General Equilibrium
      • 5.6.2 Distributed Search for a General Equilibrium
      • 5.6.3 Speculative Strategies in Equilibrium Markets
    • 5.7 Contract Nets
      • 5.7.1 Task Allocation Negotiation
      • 5.7.2 Contingency Contracts and Leveled Commitment Contracts
    • 5.8 Coalition Formation
      • 5.8.1 Coalition Formation Activity 1: Coalition Structure Generation
      • 5.8.2 Coalition Formation Activity 2: Optimization within a Coalition
      • 5.8.3 Coalition Formation Activity 3: Payoff Division
    • 5.9 Conclusions
    • 5.10 Exercises
    • 5.11 References
  • 6 Learning in Multiagent Systems
    • 6.1 Introduction
      • 6.2 A General Characterization
      • 6.2.1 Principal Categories
      • 6.2.2 Differencing Features
      • 6.2.3 The Credit-Assignment Problem
    • 6.3 Learning and Activity Coordination
      • 6.3.1 Reinforcement Learning
      • 6.3.2 Isolated, Concurrent Reinforcement Learners
      • 6.3.3 Interactive Reinforcement Learning of Coordination
    • 6.4 Learning about and from Other Agents
      • 6.4.1 Learning Organizational Roles
      • 6.4.2 Learning in Market Environments
      • 6.4.3 Learning to Exploit an Opponent
    • 6.5 Learning and Communication
      • 6.5.1 Reducing Communication by Learning
      • 6.5.2 Improving Learning by Communication
    • 6.6 Conclusions
    • 6.7 Exercises
    • 6.8 References
  • 7 Computational Organization Theory
    • 7.1 Introduction
      • 7.1.1 What Is an Organization?
      • 7.1.2 What Is Computational Organization Theory?
      • 7.1.3 Why Take a Computational Approach?
    • 7.2 Organizational Concepts Useful in Modeling Organizations
      • 7.2.1 Agent and Agency
      • 7.2.2 Organizational Design
      • 7.2.3 Task
      • 7.2.4 Technology
    • 7.3 Dynamics
    • 7.4 Methodological Issues
      • 7.4.1 Virtual Experiments and Data Collection
      • 7.4.2 Validation and Verification
      • 7.4.3 Computational Frameworks
    • 7.5 Conclusions
    • 7.6 Exercises
    • 7.7 References
  • 8 Formal Methods in DAI: Logic-Based Representation and Reasoning
    • 8.1 Introduction
    • 8.2 Logical Background
      • 8.2.1 Basic Concepts
      • 8.2.2 Propositional and Predicate Logic
      • 8.2.3 Modal Logic
      • 8.2.4 Deontic Logic
      • 8.2.5 Dynamic Logic
      • 8.2.6 Temporal Logic
    • 8.3 Cognitive Primitives
      • 8.3.1 Knowledge and Beliefs
      • 8.3.2 Desires and Goals
      • 8.3.3 Intentions
      • 8.3.4 Commitments
      • 8.3.5 Know-How
      • 8.3.6 Sentential and Hybrid Approaches
      • 8.3.7 Reasoning with Cognitive Concepts
    • 8.4 BDI Implementations
      • 8.4.1 Abstract Architecture
      • 8.4.2 Practical System
    • 8.5 Coordination
      • 8.5.1 Architecture
      • 8.5.2 Specification Language
      • 8.5.3 Common Coordination Relationships
    • 8.6 Communications
      • 8.6.1 Semantics
      • 8.6.2 Ontologies
    • 8.7 Social Primitives
      • 8.7.1 Teams and Organizational Structure
      • 8.7.2 Mutual Beliefs and Joint Intentions
      • 8.7.3 Social Commitments
      • 8.7.4 Group Know-How and Intentions
    • 8.8 Tools and Systems
      • 8.8.1 Direct Implementations
      • 8.8.2 Partial Implementations
      • 8.8.3 Traditional Approaches
    • 8.9 Conclusions
      • 8.10 Exercises
      • 8.11 References
  • 9 Industrial and Practical Applications of DAIH.
    • 9.1 Introduction
    • 9.2 Why Use DAI in Industry?
    • 9.3 Overview of the Industrial Life-Cycle
    • 9.4 Where in the Life Cycle Are Agents Used?
      • 9.4.1 Questions that Matter
      • 9.4.2 Agents in Product Design
      • 9.4.3 Agents in Planning and Scheduling
      • 9.4.4 Agents in Real-Time Control
    • 9.5 How Does Industry Constrain the Life Cycle of an Agent-Based System?
      • 9.5.1 Requirements, Positioning, and Specification
      • 9.5.2 Design: The Conceptual Context
      • 9.5.3 Design: The Process
      • 9.5.4 System Implementation
      • 9.5.5 System Operation
    • 9.6 Development Tools
    • 9.7 Conclusions
    • 9.8 Exercises
    • 9.9 References
• Part II: Related Themes
  • 10 Groupware and Computer Supported Cooperative Work
    • 10.1 Introduction
    • 10.1.1 Well-Known Groupware Examples
    • 10.2 Basic Definitions
      • 10.2.1 Groupware
      • 10.2.2 Computer Supported Cooperative Work
    • 10.3 Aspects of Groupware
      • 10.3.1 Keepers
      • 10.3.2 Coordinators
      • 10.3.3 Communicators
      • 10.3.4 Team-Agents
      • 10.3.5 Agent Models
      • 10.3.6 An Example of Aspect Analysis of a Groupware
    • 10.4 Multi-Aspect Groupware
      • 10.4.1 Chautauqua — A Multi-Aspect System
    • 10.5 Social and Group Issues in Designing Groupware Systems
    • 10.6 Supporting Technologies and Theories
      • 10.6.1 Keepers
      • 10.6.2 Coordinators
      • 10.6.3 Communicators
      • 10.6.4 Team-Agents
    • 10.7 Other Taxonomies of Groupware
      • 10.7.1 Space/Time Matrix
      • 10.7.2 Application Area
    • 10.8 Groupware and Internet
      • 10.8.1 Internet as Infrastructure
      • 10.8.2 Internet as Presumed Software
    • 10.9 Conclusions
      • 10.9.1 Incorporating Communicators into Keepers
      • 10.9.2 Incorporating Keepers and Communicators into Coordinators
      • 10.9.3 Future Research on Agents
      • 10.9.4 Future Research on Keepers
    • 10.10 Exercises
    • 10.11 References
  • 11 Distributed Models for Decision Support
    • 11.1 Introduction
    • 11.2 Decision Support Systems
      • 11.2.1 The Decision Support Problem
      • 11.2.2 Knowledge-Based Decision Support
      • 11.2.3 Distributed Decision Support Models
    • 11.3 An Agent Architecture for Distributed Decision Support Systems
      • 11.3.1 Information Model
      • 11.3.2 Knowledge Model
      • 11.3.3 Control Model
    • 11.4 Application Case Studies
      • 11.4.1 Environmental Emergency Management
      • 11.4.2 Energy Management
      • 11.4.3 Road Traffic Management
    • 11.5 Couclusions
    • 11.6 Exercises
    • 11.7 References
  • 12 Concurrent Programming for DAI
    • 12.1 Introduction
    • 12.2 Defining Multiagent Systems
    • 12.3 Actors
      • 12.3.1 Semantics of Actors
      • 12.3.2 Equivalence of Actor Systems
      • 12.3.3 Actors and Concurrent Programming
    • 12.4 Representing Agents as Actors
      • 12.4.1 Mobility of Actors
      • 12.4.2 Resource Model
    • 12.5 Agent Ensembles -12.5.1 Customizing Execution Contexts -12.5.2 Interaction Protocols -12.5.3 Coordination -12.5.4 Naming and Groups
    • 12.6 Related Work
    • 12.7 Conclusions
    • 12.8 Exercises
    • 12.9 References
  • 13 Distributed Control Algorithms for AI
    • 13.1 Introduction 13.1.1 Model of Computation 13.1.2 Complexity Measures 13.1.3 Examples of Distributed Architectures in AI
    • 13.2 Graph Exploration 13.2.1 Depth-First Search 13.2.2 Pseudo-Fast Exploration: the Echo Algorithm 13.2.3 Searching for Connectivity Certificates
    • 13.3 Termination Detection 13.3.1 Problem Definition 13.3.2 Tracing Algorithms 13.3.3 Probe Algorithms
    • 13.4 Distributed Arc Consistency and the Constraint Satisfaction Problem (CSP) 13.4.1 Constraint Satisfaction and Arc Consistency 13.4.2 The AC4 Algorithm 13.4.3 The Distributed AC4 Algorithm 13.4.4 Termination Detection 13.4.5 Partitioning for Multiprocessor Computers 13.4.6 Distributed Constraint Satisfaction Algorithm
    • 13.5 Distributed Graph Processing 13.5.1 The Problem: Loop Cutset 13.5.2 Distributed Execution of the Algorithm 13.5.3 Complexity and Conclusions
    • 13.6 Conclusions
    • 13.7 Exercises
    • 13.8 References

Notes

loop:
  - perceive                      P = perceive
  - revise knowledge              B = belief_revision(B, P)
  - reason about knowledge 
    to obtain current desires     D = option_selection(B)
  - reconsider intentions 
    based on desires and beliefs  I = intention_selection(B, D, I)
  - planning                      A = action_selection(B, I)
  - act and communicate

  +-----+      +----------+      +---+
  |     |----->| belief   |----->| B |-------------+
  |  E  |      | revision |      +-+-+             |
  |  N  |      +----------+        |               |
  |  V  |                          |               |
  |  I  |          +---------------+               |
  |  R  |          |                               |
  |  O  |          v                               v
  |  N  |     +-----------+       +---+      +-----------+
  |  M  |     | intention |<------| D |<-----| option    |
  |  E  |     | selection |       +---+      | selection | 
  |  N  |     +-----------+                  +-----------+
  |  T  |          ^                               ^
  |     |          |                               |
  |     |          +----------------+              |
  |     |                           |              |
  |     |                           v              |
  |     |     +-----------+       +---+            |
  |     |<----| action    |<------| I |------------+
  |     |     | selection |       +---+
  +-----+     +-----------+

Los deseos y las intenciones comparten sus elementos, ya que la seleccion de intenciones 'filtra' a los deseos que el agente ha seleccionado. Por lo tanto las intenciones en un ciclo deliberativo seran un subconjunto de los deseos.

Wikipedia

Provides a mechanism for separating the activity of selecting a plan (from a plan library or an external planner application) from the execution of currently active plans.

Consequently, BDI agents are able to balance the time spent on deliberating about plans (choosing what to do) and executing those plans (doing it).

A third activity, creating the plans in the first place (planning), is not within the scope of the model, and is left to the system designer and programmer.

Bratman

Implements the notions of belief, desire and (in particular) intention. Intention and desire are both pro-attitudes (mental attitudes concerned with action), but intention is distinguished as a conduct-controlling pro-attitude.

He identifies commitment as the distinguishing factor between desire and intention, noting that it leads to (1) temporal persistence in plans and (2) further plans being made on the basis of those to which it is already committed.

Temporal persistence, in the sense of explicit reference to time, is not explored. The hierarchical nature of plans is more easily implemented: a plan consists of a number of steps, some of which may invoke other plans.

The hierarchical definition of plans itself implies a kind of temporal persistence, since the overarching plan remains in effect while subsidiary plans are being executed.

The BDI software model is closely associated with intelligent agents, but does not, of itself, ensure all the characteristics associated with such agents. For example, it allows agents to have private beliefs, but does not force them to be private.

It also has nothing to say about agent communication. Ultimately, the BDI software model is an attempt to solve a problem that has more to do with plans and planning (the choice and execution thereof) than it has to do with the programming of intelligent agents.

Beliefs

Beliefs represent the informational state of the agent, in other words its beliefs about the world (including itself and other agents). Beliefs can also include inference rules, allowing forward chaining to lead to new beliefs. Using the term belief rather than knowledge recognizes that what an agent believes may not necessarily be true (and in fact may change in the future).

Beliefset

Beliefs are stored in database (sometimes called a belief base or a belief set), although that is an implementation decision.

Desires

Desires represent the motivational state of the agent. They represent objectives or situations that the agent would like to accomplish or bring about. Examples of desires might be: find the best price, go to the party or become rich.

Goals

A goal is a desire that has been adopted for active pursuit by the agent. Usage of the term goals adds the further restriction that the set of active desires must be consistent. For example, one should not have concurrent goals to go to a party and to stay at home - even though they could both be desirable.

Intentions

Intentions represent the deliberative state of the agent - what the agent has chosen to do. Intentions are desires to which the agent has to some extent committed. In implemented systems, this means the agent has begun executing a plan.

Plans

Plans are sequences of actions (recipes or knowledge areas) that an agent can perform to achieve one or more of its intentions. Plans may include other plans: my plan to go for a drive may include a plan to find my car keys. This reflects that in Bratman's model, plans are initially only partially conceived, with details being filled in as they progress.

Events

These are triggers for reactive activity by the agent. An event may update beliefs, trigger plans or modify goals. Events may be generated externally and received by sensors or integrated systems. Additionally, events may be generated internally to trigger decoupled updates or plans of activity.

BDI Interpreter

This section defines an idealized BDI interpreter that provides the basis of the PRS linage of BDI systems:

1. initialize-state
2. repeat
   1. options: option-generator(event-queue)
   2. selected-options: deliberate(options)
   3. update-intentions(selected-options)
   4. execute()
   5. get-new-external-events()
   6. drop-unsuccessful-attitudes()
   7. drop-impossible-attitudes()
3. end repeat

Limitations and Criticisms

The BDI software model is one example of a reasoning architecture for a single rational agent, and one concern in a broader multi-agent system. This section bounds the scope of concerns for the BDI software model, highlighting known limitations of the architecture.

• Learning: BDI agents lack any specific mechanisms within the architecture to learn from past behavior and adapt to new situations[6][7].
• Three Attitudes: Classical decision theorists and planning research questions the necessity of having all three attitudes, distributed AI research questions whether the three attitudes are sufficient[1].
• Logics: The multi-modal logics that underlie BDI (that do not have complete axiomatizations and are not efficiently computable) have little relevance in practice[1][8].
• Multiple Agents: In addition to not explicitly supporting learning, the framework may not be appropriate to learning behavior. Further, the BDI model does not explicitly describe mechanisms for interaction with other agents and integration into a multi-agent system.[9].
• Explicit Goals: Most BDI implementations do not have an explicit representation of goals[10].
• Lookahead: The architecture does not have (by design) any lookahead deliberation or forward planning. This may not be desirable because adopted plans may use up limited resources, actions may not be reversible, task execution may take longer than forward planning, and actions may have undesirable side effects if unsuccessful[11].

Natural Language Processing

Table of Contents

• Books
  • Speech and Language Processing 2nd Ed (Daniel Jurafsky, James H. Martin)
  • Natural Language Understanding 2nd Ed (James Allen)
  • Handbook of Natural Language Processing (Indurkhya, Damerau)
  • The Handbook of Computational Linguistics and Natural Language Processing (Clark, Fox, Lappin)
  • The Oxford Handbook of Computational Linguistics (Mitkov)
  • Foundations of Statistical Natural Language Processing (Manning, Schuetze)
  • Big Data Analytics Methods: Modern Analytics Techniques for the 21st Century: The Data Scientist’s Manual to Data Mining, Deep Learning & Natural Language Processing (Ghavami)
  • Natural Language Processing with Python: Analyzing Text with the Natural Language Toolkit (Bird, Klein, Loper)
  • Natural Language Processing with PyTorch (Rao, McMahan)
  • Neural Network Methods for Natural Language Processing (Goldberg)
  • Linguistic Fundamentals for Natural Language Processing (Bender)
  • Natural Language Processing in Action (Lane, Hapke, Howard)
  • Practical Natural Language Processing: A Comprehensive Guide to Building Real-World NLP Systems (Majumder, Gupta, Surana)
  • Introduction to Natural Language Processing (Eisenstein)
  • Statistical Machine Translation (Koehn)
  • Statistical Methods for Speech Recognition (Jelinek)
  • Applied Text Analysis with Python (Bengfort, Bilbro, Ojeda)
• Courses

Books

Speech and Language Processing 2nd Ed (Daniel Jurafsky, James H. Martin)

• Site

One of the most widely referenced and recommended NLP books, written by Stanford University professor Dan Jurafsky and University of Colorado professor James Martin, provides a deep-dive guide on the subject of language processing. It’s intended to accompany undergraduate or advanced graduate courses in NLP or Computational Linguistics. However, it’s a must-read for anyone diving into the theory and application of language processing as they grow and strengthen their analytics capabilities.

It is one of the most sought after and famously referenced and recommended books in the field of NLP. It is authored by Professor Dan Jurafsky from Stanford and James Martin from the University of Colorado. It will give you a deep understanding of the subject of natural language processing. It’s focused on supporting undergraduate or master’s courses in NLP or Computational Linguistics. It is considered as a must-read for those who are diving into the theory and it’s application part of language processing as they rise towards acquiring the skills necessary to strengthen their analytics abilities. A deep focus on web-based language approach, distinct field merging phone-based systems for dialogues, etc. Practical applications are emphasized with technical evaluation. This second edition is much more goal-oriented and can be considered as an extended version of the previous book.

This book provides coverage of NLP from both speech and text perspectives with a strong focus on applications (one in each chapter).

Coverage of the topic feels exhaustive.

Book Contents:

• Introduction
• Regular Expressions and Automata
• Words and Transducers
• N-grams
• Part-of-Speech Tagging
• Hidden Markov and Maximum Entropy Models
• Phonetics
• Speech Synthesis
• Automatic Speech Recognition
• Speech Recognition: Advanced Topics
• Computational Phonology
• Formal Grammars of English
• Syntactic Parsing
• Statistical Parsing
• Features and Unification
• Language and Complexity
• The Representation of Meaning
• Computational Semantics
• Lexical Semantics
• Computational Lexical Semantics
• Computational Discourse
• Information Extraction
• Question Answering and Summarization
• Dialog and Conversational Agents
• Machine Translation

Natural Language Understanding 2nd Ed (James Allen)

This book is another introductory guide to NLP and considered a classic. While it was published in 1994, it’s highly relevant to today’s discussions and analytics activities and lauded by generations of NLP researchers and educators. It introduces major techniques and concepts required to build NLP systems, and goes into the background and theory of each without overwhelming readers in technical jargon.

This book is a classic material on this subject of NLP. This is a revision of the original book that offers a comprehensive introductory information to natural language understanding with the latest research and developments in the field today. When compared with the first edition of superior understanding and subjective foundation, the new edition provides the learners and readers with the same kind of balanced description of syntax, semantics, and discourse, and concentrates on a uniform framework determined on feature-based context-free grammar and chart Parsers utilized for semantic and syntactic processing. Extensive treatment of problems and issues in discourse and context-dependent explanation is also given.

Handbook of Natural Language Processing (Indurkhya, Damerau)

This comprehensive, modern “Handbook of Natural Language Processing” offers tools and techniques for developing and implementing practical NLP in computer systems. There are three sections to the book: classical techniques (including symbolic and empirical approaches), statistical approaches in NLP, and multiple applications—from information visualization to ontology construction and biomedical text mining.

The second edition has a multilingual scope, accommodating European and Asian languages besides English, plus there’s greater emphasis on statistical approaches. Furthermore, it features a new applications section discussing emerging areas such as sentiment analysis. It’s a great start to learn how to apply NLP to computer systems.

The Handbook of Computational Linguistics and Natural Language Processing (Clark, Fox, Lappin)

Similar to the “Handbook of Natural Language Processing,” this book includes an overview of concepts, methodologies, and applications in NLP and Computational Linguistics, presented in an accessible, easy-to-understand way. It features an introduction to major theoretical issues and the central engineering applications that NLP work has produced to drive the discipline forward. Theories and applications work hand in hand to show the relationship in language research as noted by top NLP researchers. It’s a great resource for NLP students and engineers developing NLP applications in labs at software companies.

The Oxford Handbook of Computational Linguistics (Mitkov)

This handbook describes major concepts, methods, and applications in computational linguistics in a way that undergraduates and non-specialists can comprehend. It’s a state-of-the-art reference to one of the most active and productive fields in linguistics. A wide range of linguists and researchers in fields such as informatics, artificial intelligence, language engineering, and cognitive science will find it interesting and practical. It begins with linguistic fundamentals, followed by an overview of current tasks, techniques, and tools in Natural Language Processing that target more experienced computational language researchers.

Foundations of Statistical Natural Language Processing (Manning, Schuetze)

Another book that hails from Stanford educators, this one is written by Jurafsky’s colleague, Christopher Manning. They’ve taught the popular NLP introductory course at Stanford. Manning’s co-author is a professor of Computational Linguistics at the German Ludwig-Maximilians-Universität.

The book provides an introduction to statistical methods for NLP and a decent foundation to comprehend new NLP methods and support the creation of NLP tools. Mathematical and linguistic foundations, plus statistical methods, are equally represented in a way that supports readers in creating language processing applications.

This foundational book is the first detailed oriented introductory book of statistical natural language processing (NLP) to occur in the market. This book has all the theory and algorithms required for developing NLP tools. Statistical natural-language processing is, one of the most fast-moving and exciting branches of computer science nowadays. Learners or Practitioners and students who want to know this field would be advised to buy this book. It can be called as the most well-thumbed books to be considered for this topic. It gives a broad and deep coverage of mathematical and linguistic basics, as well as in-detail discussions of statistical methods, allowing all the students, learners, and researchers to construct their implementations. The book details the concepts of collocation findings, probabilistic parsing, data retrieval, and other applications.

This book provides an introduction to statistical methods for natural language processing covering both the required linguistics and the newer (at the time, circa 1999) statistical methods.

This book provides a strong foundation to better grasp the newer methods and encodings.

Book contents:

• Introduction
• Mathematical Foundations
• Linguistic Essentials
• Corpus-Based Work
• Collocations
• Statistical Inference: n-gram Models over Sparse Data
• Word Sense Disambiguation
• Lexical Acquisition
• Markov Models
• Part-of-Speech Tagging
• Probabilistic Context Free Grammars
• Probabilistic Parsing
• Statistical Alignment and Machine Translation
• Clustering
• Topics in Information Retrieval
• Text Categorization

Big Data Analytics Methods: Modern Analytics Techniques for the 21st Century: The Data Scientist’s Manual to Data Mining, Deep Learning & Natural Language Processing (Ghavami)

Peter’s book might seem daunting to a NLP newcomer, but it’s useful as a comprehensive manual for those familiar with NLP and how big data relates in today’s world. It also works as a helpful reference for data scientists, analysts, business managers, and Business Intelligence practitioners. With more than a hundred analytics techniques and methods included, we think this will be a favorite for seasoned analytics practitioners.

Chapters cover everything from machine learning to predictive modeling and cluster analysis. Data science topics including data visualization, prediction, and regression analysis, plus NLP-related fields such as neural networks, deep learning, and artificial intelligence are also discussed. These come with a broad explanation, but Peter goes into more detail about terminology and mathematical foundations, too.

Natural Language Processing with Python: Analyzing Text with the Natural Language Toolkit (Bird, Klein, Loper)

• Site

This book is a helpful introduction to the NLP field with a focus on programming. If you want have a practical source on your shelf or desk, whether you’re a NLP beginner, computational linguist or AI developer, it contains hundreds of fully-worked examples and graded exercises that bring NLP to life. It can be used for individual study, as a course textbook when studying NLP or computational linguistics, or in complement with artificial intelligence, text mining, or corpus linguistics courses.

Curious about Python programming language? It will walk you through creating Python programs that parse unstructured data like language and recommends downloading Python and the Natural Language Toolkit. On a companion site, the authors have actually updated the book to work with Python 3 and NLTK 3.

A great starting spot for learning the practical basics of natural language processing from the point of view of the Python ecosystem. Also known as the NLTK Book, Natural Language Processing with Python leans heavily on the NLTK library throughout, which is a useful piece of software for learning purposes.

From the book's preface:

• This book provides a highly accessible introduction to the field of NLP.
• It can be used for individual study or as the textbook for a course on natural language processing or computational linguistics, or as a supplement to courses in artificial intelligence, text mining, or corpus linguistics. The book is intensely practical, containing hundreds of fully-worked examples and graded exercises.
• [...]
• This book is intended for a diverse range of people who want to learn how to write programs that analyze written language, regardless of previous programming experience.

The book is definitely of a practical nature. While you will assuredly have concepts explained as you go, there is little doubt that the book is crafted as a launchpad for those looking to get going with implementing NLP solutions with Python, and doing so now.

This is one of the Best book for Natural Language Processing. This book will give you introduction to Natural Language Processing using Python and Python NLTK Library.

With the help of this book, you will learn how to write Python programs that work with large collections of unstructured text.

Book contents:

• Language Processing and Python
• Accessing Text Corpora and Lexical Resources
• Processing Raw Text
• Writing Structured Programs
• Categorizing and Tagging Words
• Learning to Classify Text
• Extracting Information from Text
• Analyzing Sentence Structure
• Building Feature-Based GRammars
• Analyzing the Meaning of Sentences
• Managing Linguistic Data

Natural Language Processing with PyTorch (Rao, McMahan)

This book moves on from traditional NLP techniques to those using neural networks. A practical approach to the subject, it jumps straight into applying neural network NLP methods using PyTorch.

Directly from the book's website, some of the topics covered include:

• Explore computational graphs and the supervised learning paradigm
• Master the basics of the PyTorch optimized tensor manipulation library
• Get an overview of traditional NLP concepts and methods
• Learn the basic ideas involved in building neural networks
• Use embeddings to represent words, sentences, documents, and other features
• Explore sequence prediction and generate sequence-to-sequence models
• Learn design patterns for building production NLP systems

This is a great starting point for transitioning from more traditional (non-neural network based) NLP techniques to those which have consumed the field in the past few years, which are heavily reliant on deep learning.

Neural Network Methods for Natural Language Processing (Goldberg)

This book is authored by Yoav Goldberg and can be considered only as an Introductory textbook. Neural networks are known as a family of powerful machine learning models. This book sole emphasis is on the application of neural network models to natural language data. The first 50 percent of the book covers all the basics of supervised machine learning and feed-forward neural networks, the fundamentals of working with machine learning over language-based data, and the usage of vector-based data rather than symbolic rendering for words. It also focuses on the computation-graph abstraction, that allows to define and train arbitrary neural networks with ease and is the important basis behind the design of modern neural network software libraries.

Yoav Goldberg writes this book on neural network methods for NLP. You may have begun implementing such methods using the previous book, and while "Natural Language Processing with PyTorch" does a fine job of outlining the intuitions behind its methods, Goldberg's book takes a deeper dive into explaining these concepts without the burden of implementing them in code.

From the book's website:

• This book focuses on the application of neural network models to natural language data.
• The first half of the book (Parts I and II) covers the basics of supervised machine learning and feed-forward neural networks, the basics of working with machine learning over language data, and the use of vector-based rather than symbolic representations for words.
• [...]
• The second part of the book (Parts III and IV) introduces more specialized neural network architectures, including 1D convolutional neural networks, recurrent neural networks, conditioned-generation models, and attention-based models. These architectures and techniques are the driving force behind state-of-the-art algorithms for machine translation, syntactic parsing, and many other applications.

Firmly in the realm of the theoretical or explanatory, Neural Network Methods for Natural Language Processing will go a long way to shoring up your understanding of how modern neural network based approaches to NLP work, and why they are employed.

This book covers the application of neural network models to natural language processing tasks. In that book, you will learn about basics of supervised machine learning and feed-forward neural networks.

Along with that, you will also learn neural network architectures, including 1D convolutional neural networks, recurrent neural networks, conditioned-generation models, and attention-based models.

Linguistic Fundamentals for Natural Language Processing (Bender)

Of course, flying blind with respect to linguistic fundamentals is not a great idea when working with NLP, and can be of special concern when approaching NLP or computational linguistics from the purely computational side, lacking any formal study in linguistics. This book by Emily M. Bender seeks to help bridge this gap.

The book's website describes the book's purpose as such:

The purpose of this book is to present in a succinct and accessible fashion information about the morphological and syntactic structure of human languages that can be useful in creating more linguistically sophisticated, more language-independent, and thus more successful NLP systems.

Bender backs this up with the following from Chapter 1:

[K]nowledge about linguistic structures can inform the design of features for machine learning approaches to NLP. Put more strongly: knowledge of linguistic structure will lead to the design of better features for machine learning.

The book is organized as 100 individual "essentials" for better understanding morphology and syntax, with the essentials grouped into chapters of related topics. If you do not have a linguistics background (I do not), this book may be a painstaking read (it is supposed to be) but will undoubtedly lead to a better linguistic understanding you can put to use in your NLP career.

Natural Language Processing in Action (Lane, Hapke, Howard)

This book Natural Language Processing in Action is your guide to developing machines that can read and interpret the language used by humans. Within this, you’ll use obtainable Python packages to encapsulate the understanding in text and react to it. This book extends conventional NLP ways to include neural networks, modern deep learning algorithms, and major generative techniques when you tackle real-world issues like extracting names, places and dates, text composing, and free-form answering of listed questionnaires. You will just need a basic understanding of deep learning and intermediate-level Python knowledge. This book also shows how to work with Keras, TensorFlow, Gensim, and SCIkit including scalable pipelines and rule-based NLP. So get this book and Learn all the theory and practical skills necessary to go further by merely understanding the inner functioning of NLP, and start developing your own algorithms and models.

This book is a return to the practical. Covering both traditional and neural network based approaches to NLP, Natural Language Processing in Action could be considered a combination of the first 2 books in this list, covering practical coding solutions using modern tools such as TensorFlow and Keras, among others.

From the book's website:

• Natural Language Processing in Action is your guide to building machines that can read and interpret human language.
• In it, you’ll use readily available Python packages to capture the meaning in text and react accordingly.
• The book expands traditional NLP approaches to include neural networks, modern deep learning algorithms, and generative techniques as you tackle real-world problems like extracting dates and names, composing text, and answering free-form questions.

As a consequence of being the most recently released book in this list (just narrowly edging out Natural Language Processing with PyTorch) as well as that with the most pages, it is likely the most up-to-date and comprehensive practical book in this list, and perhaps even currently available on the market. But that doesn't mean it should be your default choice here either; it depends on the ecosystem you want to work in, and the level of detail you are looking to gain, among other considerations.

As its name suggests “Natural Language Processing in Action”, it’s another best practical approach book for NLP. In that book, you will learn how to build machines that can read and interpret human language.

The authors of this books are experienced NLP engineers. In that book, you will learn how to use readily available Python packages to capture the meaning in text and react accordingly.

Book contents:

• PART 1 – WORDY MACHINES
  • Packets of thought (NLP overview)
  • Build your vocabulary (word tokenization)
  • Math with words (TF-IDF vectors)
  • Finding meaning in word counts (semantic analysis)
• PART 2 – DEEPER LEARNING (NEURAL NETWORKS)
  • Baby steps with neural networks (perceptrons and backpropagation)
  • Reasoning with word vectors (Word2vec)
  • Getting words in order with convolutional neural networks (CNNs)
  • Loopy (recurrent) neural networks (RNNs)
  • Improving retention with long short-term memory networks
  • Sequence-to-sequence models and attention
• PART 3 – GETTING REAL (REAL-WORLD NLP CHALLENGES)
  • Information extraction (named entity extraction and question answering)
  • Getting chatty (dialog engines)
  • Scaling up (optimization, parallelization, and batch processing)

Practical Natural Language Processing: A Comprehensive Guide to Building Real-World NLP Systems (Majumder, Gupta, Surana)

This book provides a comprehensive point-based description of building real-world NLP applications. It will guide you through the process of developing Authentic NLP solutions placed and used in a larger product system. This guide is practical for people who want to develop, manage, and scale NLP systems in a major business environment and modify them for niche industries. You will also learn how to adapt to the various industry verticals such as healthcare, Media, and retail, etc. At the end of this book, you will Understand the wide range of problems, tasks, and different approaches within NLP. Also, you will learn to Perfectly Implement and evaluate different NLP applications machine learning methods. Evaluate all the different algorithms and approaches for NLP product tasks and datasets. Develop and create software solutions by maintaining the best practices during release, deployment, and DevOps for Natural Language Processing systems.

Introduction to Natural Language Processing (Eisenstein)

This book gives a technical direction on the subject of natural language processing―the different ways for developing computer software that understands, produces, and manipulates the language of humans. It emphasizes recent data-driven approaches, attentive towards the techniques from supervised and non-supervised machine learning. Starting with the first section of the book that creates a basic ideation into machine learning by developing a set of tools that can be used throughout the book and application of those for practical word-based textual analysis. This book provides a superb introduction to natural language processing, with the main emphasis on foundational method building and algorithms.

Statistical Machine Translation (Koehn)

This book will give you an introduction to statistical machine translation that is a sub-field of Natural Language Processing.

Book contents:

• Introduction
• Words, Sentences, Corpa
• Probability Theory
• Word-Based Models
• Phrase-Based Models
• Decoding
• Language Models
• Evaluation
• Discriminative Training
• Integrating Linguistic Information
• Tree-Based Methods

Statistical Methods for Speech Recognition (Jelinek)

This book will give you an introduction to the topic of statistical speech recognition, another most popular application of Natural Language Processing. In that book, you will find a thorough introduction to speech recognition.

Book contents:

• The Speech Recognition Problem
• Hidden Markov Models
• The Acoustic Model
• Basic Language Modeling
• The Viterbi Search
• Hypothesis Search on a Tree and the Fast Match
• Elements of Information Theory
• The Complexity of Tasks – The Quality of Language Models
• The Expectation-Maximization Algorithm and Its Consequences
• Decision Trees and Tree Language Models
• Phonetics from Orthography: Spelling-to-Base Form Mappings
• Triphones and Allophones
• Maximum Entropy Probability Estimation and Language Models
• Tree Applications of Maximum Entropy Estimation to Language Modeling
• Estimation of Probabilities from Counts and the Back-Off Method

Applied Text Analysis with Python (Bengfort, Bilbro, Ojeda)

In this book, you will learn robust, repeatable, and scalable techniques for text analysis with Python, including contextual and linguistic feature engineering, vectorization, classification, topic modeling, entity resolution, graph analysis, and visual steering.

Along with that, you will also learn how to perform document classification and topic modeling. This book will teach you how to build a dialog framework to enable chatbots and language-driven interaction. Why this Book is Good?

This book will give you a data scientist’s perspective on building language-aware products with applied machine learning techniques.

Courses

• Stanford's Natural Language Processing with Deep Learning (CS224n)

Richard Sutton

Source

Table of Contents

• What's Wrong with Artificial Intelligence
• Verification, The Key to AI
• Verification
• Mind is About Information
  • Mind is Computational, not Material
  • Mind is Purposive
• Mind Is About Conditional Predictions
• Subjective Knowledge
• Fourteen Declarative Principles of Experience-Oriented Intelligence
• The Definition of Intelligence
• The Bitter Lesson

What's Wrong with Artificial Intelligence

Source November 12, 2001

I hold that AI has gone astray by neglecting its essential objective --- the turning over of responsibility for the decision-making and organization of the AI system to the AI system itself. It has become an accepted, indeed lauded, form of success in the field to exhibit a complex system that works well primarily because of some insight the designers have had into solving a particular problem. This is part of an anti-theoretic, or "engineering stance", that considers itself open to any way of solving a problem. But whatever the merits of this approach as engineering, it is not really addressing the objective of AI. For AI it is not enough merely to achieve a better system; it matters how the system was made. The reason it matters can ultimately be considered a practical one, one of scaling. An AI system too reliant on manual tuning, for example, will not be able to scale past what can be held in the heads of a few programmers. This, it seems to me, is essentially the situation we are in today in AI. Our AI systems are limited because we have failed to turn over responsibility for them to them.

Please forgive me for this which must seem a rather broad and vague criticism of AI. One way to proceed would be to detail the criticism with regard to more specific subfields or subparts of AI. But rather than narrowing the scope, let us first try to go the other way. Let us try to talk in general about the longer-term goals of AI which we can share and agree on. In broadest outlines, I think we all envision systems which can ultimately incorporate large amounts of world knowledge. This means knowing things like how to move around, what a bagel looks like, that people have feet, etc. And knowing these things just means that they can be combined flexibly, in a variety of combinations, to achieve whatever are the goals of the AI. If hungry, for example, perhaps the AI can combine its bagel recognizer with its movement knowledge, in some sense, so as to approach and consume the bagel. This is a cartoon view of AI -- as knowledge plus its flexible combination -- but it suffices as a good place to start. Note that it already places us beyond the goals of a pure performance system. We seek knowledge that can be used flexibly, i.e., in several different ways, and at least somewhat independently of its expected initial use.

With respect to this cartoon view of AI, my concern is simply with ensuring the correctness of the AI's knowledge. There is a lot of knowledge, and inevitably some of it will be incorrrect. Who is responsible for maintaining correctness, people or the machine? I think we would all agree that, as much as possible, we would like the AI system to somehow maintain its own knowledge, thus relieving us of a major burden. But it is hard to see how this might be done; easier to simply fix the knowledge ourselves. This is where we are today.

Verification, The Key to AI

Source November 15, 2001

It is a bit unseemly for an AI researcher to claim to have a special insight or plan for how his field should proceed. If he has such, why doesn't he just pursue it and, if he is right, exhibit its special fruits? Without denying that, there is still a role for assessing and analyzing the field as a whole, for diagnosing the ills that repeatedly plague it, and to suggest general solutions.

The insight that I would claim to have is that the key to a successful AI is that it can tell for itself whether or not it is working correctly. At one level this is a pragmatic issue. If the AI can't tell for itself whether it is working properly, then some person has to make that assessment and make any necessary modifications. An AI that can assess itself may be able to make the modifications itself.

The Verification Principle:

An AI system can create and maintain knowledge only to the extent that it can verify that knowledge itself.

Successful verification occurs in all search-based AI systems, such as planners, game-players, even genetic algorithms. Deep Blue, for example, produces a score for each of its possible moves through an extensive search. Its belief that a particular move is a good one is verified by the search tree that shows its inevitable production of a good position. These systems don't have to be told what choices to make; they can tell for themselves. Image trying to program a chess machine by telling it what kinds of moves to make in each kind of position. Many early chess programs were constructed in this way. The problem, of course, was that there were many different kinds of chess positions. And the more advice and rules for move selection given by programmers, the more complex the system became and the more unexpected interactions there were between rules. The programs became brittle and unreliable, requiring constant maintainence, and before long this whole approach lost out to the "brute force" searchers.

Although search-based planners verify at the move selection level, they typically cannot verify at other levels. For example, they often take their state-evaluation scoring function as given. Even Deep Blue cannot search to the end of the game and relies on a human-tuned position-scoring function that it does not assess on its own. A major strength of the champion backgammon program, TD-Gammon, is that it does assess and improve its own scoring function.

Another important level at which search-based planners are almost never subject to verification is that which specifies the outcomes of the moves, actions, or operators. In games such as chess with a limited number of legal moves we can easily imagine programming in the consequences of all of them accurately. But if we imagine planning in a broader AI context, then many of the allowed actions will not have their outcomes completely known. If I take the bagel to Leslie's office, will she be there? How long will it take to drive to work? Will I finish this report today? So many of the decisions we take every day have uncertain and changing effects. Nevertheless, modern AI systems almost never take this into account. They assume that all the action models will be entered accurately by hand, even though these may be most of the knowledge in or ever produced by the system.

Finally, let us make the same point about knowledge in general. Consider any AI system and the knowledge that it has. It may be an expert system or a large database like CYC. Or it may be a robot with knowledge of a building's layout, or knowledge about how to react in various situations. In all these cases we can ask if the AI system can verify its own knowledge, or whether it requires people to intervene to detect errors and unforeseen interactions, and make corrections. As long as the latter is the case we will never be able to build really large knowledge systems. They will always be brittle and unreliable, and limited in size to what people can monitor and understand themselves.

"Never program anything bigger than your head"

And yet it is overwhelmingly the case that today's AI systems are not able to verify their own knowledge. Large ontologies and knowledge bases are built that are totally reliant on human construction and maintainence. "Birds have wings" they say, but of course they have no way of verifying this.

Verification

Source 11/14/2001

If the human designers of an AI are not to be burdened with ensuring that what their AI knows is correct, then the AI will have to ensure it itself. It will have to be able to verify the knowledge that it has gained or been given.

Giving an AI the ability to verify its knowledge is no small thing. It is in fact a very big thing, not easy to do. Often a bit of knowledge can be written very compactly, whereas its verification is very complex. It is easy to say "there is a book on the table", but very complex to express even a small part of its verification, such as the visual and tactile senations involved in picking up the book. It is easy to define an operator such as "I can get to the lunchroom by going down one floor", but to verify this one must refer to executable routines for finding and descending the stairs, recognizing the lunchroom, etc. These routines involve enormously greater detail and closed-loop contingences, such as opening doors, the possibility of a stairway being closed, or meeting someone on the way, than does the knowledge itself. One can often suppress all this detail when using the knowledge, e.g., in planning, but to verify the knowledge requires its specification at the low level. There is no comparison between the ease of adding unverified knowledge and the complexity of including a means for its autonomous verification.

Note that although all the details of execution are needed for verification, the execution details are not themselves the verification. There is a procedure for getting to the lunchroom, but separate from this would be the verifier for determining if it has succeeded. It is perfectly possible for the procedure to be fully grounded in action and sensation, while completely leaving out the verifier and thus the possibility of autonomous knowledge maintainence. At the risk of being too broad-brush about it, this is what typically happens in modern AI robotics systems. They have extensive grounded knowledge, but still no way of verifying almost any of it. They use visual routines to recognize doors and hallways, and they make decisions based on these conclusions, but they cannot themselves correct their errors. If something is recognized as a "doorway" yet cannot be passed through, this failure will not be recognized and not used to correct future doorway recognitions, unless it is done by people.

On the other hand, once one has grounding, the further step to include verification is less daunting. One need only attach to the execution procedures appropriate tests and termination conditions that measure in some sense the veracity of the original statement, while at the same time specifying what it really means in detail. What is a chair? Not just something that lights up your visual chair detector! That would be grounded knowledge, but not verifiable; it would rely on people to say which were and were not chairs. But suppose you have routines for trying to sit. Then all you need for a verifier is to be able to measure your success at sitting. You can then verify, improve, and maintain your "sittable thing" recognizer on your own.

There is a great contrast between the AI that I am proposing and what might be considered classical "database AI". There are large AI efforts to codify vast amounts of knowledge in databases or "ontologies", of which Doug Lenat's CYC is only the most widely known. In these efforts, the idea of people maintaining the knowledge is embraced. Special knowledge representation methods and tools are emphasized to make it easier for people to understand and access the knowledge, and to try to keep it right. These systems tend to emphasize static, world knowledge like "Springfield is the capital of Illinois", "a canary is a kind of bird", or even "you have a meeting scheduled with John at 3:30", rather than the dynamic knowledge needed say by a robot to interact in real time with its environment. A major problem is getting people to use the same categories and terms when they enter knowledge and, more importantly, to mean the same things by them. There is a search for an ultimate "ontology", or codification of all objects and their possible relationships, so that clear statements can be made about them. But so far this has not proven possible; there always seem to be far more cases that don't fit than do. People are good about being fluid with there concepts, and knowing when they don't apply.

Whatever the ultimate success of the symbolic "database AI" approach, it should be clear that it is the anti-thesis of what I am calling for. The database approach calls for heroic efforts organizing and entering an objective, public, and disembodied knowledge base. I am calling for an AI that maintains its own representations, perhaps different from those of others, while interacting in real time with a dynamic environment. Most important of all, the database approach embraces human maintainence and human organization of the AI's knowledge. I am calling for automating these functions, for the AI being able to understand its knowledge well enough to verify it itself.

Mind is About Information

Source 11/19/2001

What is the mind? Of course, "mind" is just a word, and we can mean anything we want by it. But if we examine the way we use the word, and think about the kinds of things we consider more mindful than others, I would argue that the idea of choice is the most important. We consider things to be more or less mindful to the extent that they appear to be making choices. To make a choice means to distinguish, and to create a difference. In this basic sense the mind is about information. Its essential function is to process bits into other bits. This position has two elements:

• Mind is Computational, not Material
• Mind is Purposive

Mind is Computational, not Material

The idea that the mind's activities are best viewed as information processing, as computation, has become predominant in our sciences over the last 40 years. People do not doubt that minds have physical, material form, of course, either as brains or perhaps as computer hardware. But, as is particularly obvious in the latter case, the hardware is often unimportant. Is is how the information flows which matters.

I like to bring this idea down to our basest intuition. What things are more mindlike and less mindlike? A thermostat is slightly mindlike. It converts a gross physical quanitity, the air temperature of your home, to a small deviation in a piece of metal, which tips a small lump of mercury which in turn triggers a fire in your furnace. Large physical events are reduced and processed as small ones, the physical is reduced to mere distinctions and processed as information. The sensors and effectors of our brains are essentially similar. Relatively powerful physical forces impinge on us, and our sensors convert them to tiny differences in nerve firings. These filter and are further processed until signals are sent to our muscles and there amplified into gross changes in our limbs and other large physical things. At all stages it is all physical, but inside our heads there are only small physical quanities that are easily altered and diverted as they interact with each other. This is what we mean by information processing. Information is not non-physical. It is a way of thinking about what is happening that is sometime much more revealing and useful than its physical properties.

Or so is one view, the view that takes a material physical reality as primary. The informational view of mind is just as compatible with alternative philosophical orientations. The one I most appreciate is that which takes the individual mind and its exchanging of information with the world as the primary and base activity. This is the so-called "buttons and lights" model, in which the mind is isolated behind an interface of output bits (buttons) and input bits (lights). In this view, the idea of the physical world is created by the mind so as to explain the pattern of input bits and how they respond to the output bits. This is a cartoon view, certainly, but a very clear one. There is no confusion about mind and body, material and ideal. There is just information, distinctions observed and differences made.

Mind is Purposive

Implicit in the idea of choice, particularly as the essense of mindfulness, is some reason or purpose for making the choices. In fact it is difficult even to talk about choice without alluding to some purpose. One could say a rock "chooses" to do nothing, but only by suggesting that its purpose is to sit still. If a device generated decisions at random one would hesitate to say that it was "choosing." No, the whole idea of choice implies purpose, a reason for making the choice.

Purposiveness is at heart of mindfulness, and the heart of purposeness is the varying of means to achieve fixed ends. William James in 1890 identified this as "the mark and criterion of mentality". He discussed an air bubble rising rising in water until trapped in an inverted jar, contrasting it with a frog, which may get trapped temporarily but keeps trying things until it finds a way around the jar. Varying means and fixed ends. In AI we call it generate and test. Or trial and error. Variation and selective survival. There are many names and many variations, but this idea is the essense of purpose, choice, and Mind.

Mind Is About Conditional Predictions

March 21, 2000

Simplifying and generalizing, one thing seems clear to me about mental activity---that the purpose of much of it can be considered to be the making of predictions. By this I mean a fairly general notion of prediction, including conditional predictions and predictions of reward. And I mean this in a sufficiently strong and specific sense to make it non-vacuous.

For concreteness, assume the world is a Markov Decision Process (MDP), that is, that we have discrete time and clear actions, sensations, and reward on each time step. Then, obviously, among the interesting predictions to make are those of immediate rewards and state transitions, as in "If I am in this state and do this action, then what will the next state and reward be?" The notion of value function is also a prediction, as in "If I am in this state and follow this policy, what will my cumulative discounted future reward be?" Of course one could make many value-function predictions, one for each of many different policies.

Note that both kinds of prediction mentioned above are conditional, not just on the state, but on action selections. They are hypothetical predictions. One is hypothetical in that it is dependent on a single action, and the other is hypothetical in that it is dependent on a whole policy, a whole way of behaving. Action conditional predictions are of course useful for actually selecting actions, as in many reinforcement learning methods in which the action with the highest estimated value is preferentially chosen. More generally, it is commonsensical that much of our knowledge is beliefs about what would happen IF we chose to behave in certain ways. The knowledge about how long it takes to drive to work, for example, is knowledge about the world in interaction with a hypothetical purposive way in which we could behave.

Now for the key step, which is simply to generalize the above two clear kinds of conditional predictions to cover much more of what we normally think of as knowledge. For this we need a new idea, a new way of conditioning predictions that I call conditioning on outcomes. Here we wait until one of some clearly designated set of outcomes occurs and ask (or try to predict) something about which one it is. For example, we might try to predict how old we will be when we finish graduate school, or how much we will weigh at the end of the summer, or how long it will take to drive to work, or much you will have learned by the time you reach the end of this article. What will the dice show when they have stopped tumbling? What will the stock price be when I sell it? In all these cases the prediction is about what the state will be when some clearly identified event occurs. It is a little like when you make a bet and establish some clear conditions at which time the bet will be over and it will be clear who has won.

A general conditional prediction, then, is conditional on three things: 1) the state in which it is made, 2) the policy for behaving, and 3) the outcome that triggers the time at which the predicted event is to occur. Of course the policy need only be followed from the time the prediction is made until the outcome triggering event. Actions taken after the trigger are irrelevant. [This notion of conditional prediction has been previously explored as the models of temporally extended actions, also known as "options" (Sutton, Precup, and Singh, 1999; Precup, thesis in preparation).

Let us return now to the claim with which I started, that much if not most mental activity is focused on such conditional predictions, on learning and computing them, on planning and reasoning with them. I would go so far as to propose that much if not most of our knowledge is represented in the form of such predictions, and that they are what philosophers refer to as "concepts". To properly argue these points would of course be a lengthy undertaking. For now let us just cover some high points, starting with some of the obvious advantages of conditional predictions for knowledge representation.

Foremost among these is just that predictions are grounded in the sense of having a clear, mechanically determinable meaning. The accuracy of any prediction can be determined just by running its policy from its state until an outcome occurs, then checking the prediction against the outcome. No human intervention is required to interpret the representation and establish the truth or falsness of any statement. The ability to compare predictions to actual events also make them suitable for beling learned automatically. The semantics of predictions also make it clear how they are to be used in automatic planning methods such as are commonly used with MDPs and SMDPs. In fact, the conditional predictions we have discussed here are of exactly the form needed for use in the Bellman equations at the heart of these methods.

A less obvious but just as important advantage of outcome-conditional predictions is that they can compactly express much that would otherwise be difficult and expensize to represent. This happens very often in commonsense knowledge; here we give a simple example. The knowledge we want to represent is that you can go to the street corner and a bus will come to take you home within an hour. What this means of course is that if it is now 12:00 then the bus might come at 12:10 and it might come at 12:20, etc., but it will definitely come by 1:00. Using outcome conditioning, the idea is easy to express: we either make the outcome reaching 1:00 and predict that the bus will have come by then, or we make the outcome the arrival of the bus and predict that at that time it will be 1:00 or earlier.

A natural but naive alternative way to try to represent this knowledge would be as a probability of the bus arriving in each time slot. Perhaps it has one-sixth chance of arriving in each 10-minute interval. This approach is unsatisfactory not just because it forces us to say more than we may know, but because it does not capture the important fact that the bus will come eventually. Formally, the problem here is that the events of the bus coming at different times are not independent. If may have only a one-sixth chance of coming exactly at 1:00, but if it is already 12:55 then it is in fact certain to come at 1:00. The naive representation does not capture this fact that is actually absolutely important to using this knowledge. A more complicated representation could capture all these dependencies but would be just that -- more complicated. The outcome-conditional form represents the fact simply and represents just what is needed to reason with the knowledge this way. Of course, other circumstances may require the more detailed knowledge, and this is not precluded by the outcome-conditional form. This form just permits greater flexibility, in particular, the ability to omit these details while still being of an appropriate form for planning and learning.

Subjective Knowledge

April 6, 2001

I would like to revive an old idea about the mind. This is the idea that the mind arises from, and is principally about, our sensori-motor interaction with the world. It is the idea that all our sense of the world, of space, objects, and other people, arises from our experience squeezed through the narrow channel of our sensation and action. This is a radical view, but in many ways an appealing one. It is radical because it says that experience is the only thing that we directly know, that all our sense of the material world is constructed to better explain our subjective experience. It is not just that the mental is made primary and held above the physical, but that the subjective is raised over the objective.

Subjectivity is the most distinctive aspect of this view of the mind, and inherent in it. If all of our understanding of the world arises from our experience, then it is inherently personal and specific to us.

As scientists and observers we are accustomed to prasing the objective and denigrating the subjective, so reversing this customary assessment requires some defense.

The approach that I am advocating might be termed the subjective viewpoint. In it, all knowledge and understanding arises out of an individual's experience, and in that sense is inherently in terms that are private, personal, and subjective. An individual might know, for example, that a certain action tends to be followed by a certain sensation, or that one sensation invariably follows another. But these are its sensations and its actions. There is no necessary relationship between them and the sensations and actions of another individual. To hypothesize such a link might be useful, but always secondary to the subjective experience itself.

The subjective view of knowledge and understanding might be constrasted with the objective, realist view. In this view there are such things as matter, physical objects, space and time, other people, etc. Things happen, and causally interact, largely independent of observers. Occasionally we experience something subjectively, but later determine that it did not really, objectively happen. For example, we felt the room get hot, but the thermometer registered no change. In this view there is a reality independent of our experience. This would be easy to deny if there were only one agent in the world. In that case it is clear that that agent is merely inventing things to explain its experience. The objective view gains much of its force because it can be shared by different people. In science, this is almost the definition of the subjective/objective distinction: that which is private to one person is subjective whereas that which can be observed by many, and replicated by others, is objective.

I hasten to say that the subjective view does not deny the existence of the physical world. The conventional physical world is still the best hypothesis for explaining our subjective data. It is just that that world is held as secondary to the data that it is used to explain. And a little more: it is that the physical world hypothesis is just that, a hypothesis, an explanation. There are not two kinds of things, the mental and the physical. There are just mental things: the data of subjective experience and hypotheses constructed to explain it.

The appeal of the subjective view is that it is grounded. Subjective experience can be viewed as data in need of explanation. There is a sense in which only the subjective is clear and unambiguous. "Whatever it means, I definitely felt warm in that room." No one can argue with our subjective experience, only with its explanation and relationship to other experiences that we have or might have. The closer the subjective is inspected, the firmer and less interpreted it appears, the more is becomes like data, whereas the objective often becomes vaguer and more complex. Consider the old saw about the person who saw red whenever everybody else saw green, and vice versa, but didn't realize it because he used the words "red" and "green" the wrong way around as well. This nonsense points out that different people's subjective experiences are not comparable. The experience that I call seeing red and the experience you call seeing red are related only in a very complicated way including, for example, effects of lighting, reflectance, viewpoint, and colored glasses. We have learned to use the same word to capture an important aspect of our separate experience, but ultimately the objective must bow to the subjective.

The appeal of the objective view is that it is common across people. Something is objectively true if it predicts the outcome of experiments that you and I both can do and get the same answer. But how is this sensible? How can we get the same answer when you see with your eyes and I with mine? For that matter, how can we do the "same" experiment? All these are problematic and require extensive theories about what is the same and what is different. In particular, they require calibration of our senses with each other. It is not just a question of us using the same words for the same things -- the red/green example shows the folly of that kind of thinking -- it is that there is no satisfactory notion of same things, across individuals, at the level of experience. Subjective experience as the ultimate data is clear, but not the idea that it can be objectively compared across persons. That idea can be made to work, approximately, but should be seen as following from the primacy of subjective experience.

At this point, you are probably wondering why I am belaboring this philosphical point. The reason is that the issue comes up, again and again, that it is difficult to avoid the pitfalls associated with the objective view without explicitly identifying them. This fate has befallen AI researchers many times in the past. So let us close with as clear a statement as we can of the implications of the subjective view for approaches to AI. What must be avoided, and what sought, in developing a subjective view of knowledge and mind?

All knowledge must be expressed in terms that are ultimately subjective, that are expressed in terms of the data of experience, of sensation and action. Thus we seek ways of clearly expressing all kinds of human knowledge in subjective terms. This is a program usually associated with the term "associationism" and often denigrated. Perhaps it is impossible, but it should be tried, and it is difficult to disprove, like a null hypothesis. In addition to expressing knowledge subjectively, we should also look to ways of learning and working with subjective knowledge. How can we reason with subjective knowledge to obtain more knowledge? How can it be tested, verified, and learned? How can goals be expressed in subjective terms?

Notes:

• McCarthy quote.
• Relate to logical positivism.
• Then Dyna as a simple example, and which highlights what is missing.

Fourteen Declarative Principles of Experience-Oriented Intelligence

1. all goals and purposes can be well thought of as the maximization of the expected value of the cumulative sum of a single externally received number (reward). “the reward hypothesis” thus life is a sequential decision-making problem, also known as a Markov decision process. “learning is adaptive optimal control”
2. a major thing that the mind does is learn a state representation and a process for updating it on a moment-by-moment basis. the input to the update process is the current sensation, action, and state (representation). “state is constructed”
3. all action is taken at the shortest possible time scale, by a reactive, moment-by-moment policy function mapping from state to action. anything higher or at longer time scales is for thinking about action, not for taking it. “all behavior is reactive”
4. all efficient methods for solving sequential decision-making problems compute, as an intermediate step, an estimate for each state of the long-term cumulative reward that follows that state (a value function). subgoals are high-value states. “values are more important than rewards”
5. a major thing that the mind does is learn a predictive model of the worldʼs dynamics at multiple time scales. this model is used to anticipate the outcome (consequences) of different ways of behavior, and then learn from them as if they had actually happened (planning).
6. learning and planning are fundamentally the same process, operating in the one case on real experience, and in the other on simulated experience from a predictive model of the world. “thought is learning from imagined experience”
7. all world knowledge can be well thought of as predictions of experience. “knowledge is prediction” in particular, all knowledge can be thought of as predictions of the outcomes of temporally extended ways of behaving, that is, policies with termination conditions, also known as “options.” these outcomes can be abstract state representations if those in turn are predictions of experience.
8. state representations, like all knowledge, should be tied to experience as much as possible. thus, the bayesian and POMDP conceptions of state estimation are mistaken.
9. temporal-difference learning is not just for rewards, but for learning about everything, for all world knowledge. any moment-by-moment signal (e.g., a sensation or a state variable) can substitute for the reward in a temporal-difference error. “TD learning is not just for rewards”
10. learning is continual, with the same processes operating at every moment, with only the content changing at different times and different levels of abstraction. “the one learning algorithm”
11. evidence adds and subtracts to get an overall prediction or action tendency. thus policy and prediction functions can be primarily linear in the state representation, with learning restricted to the linear parameters. this is possible because the state representation contains many state variables other than predictions and that are linearly independent of each other. these include immediate non-linear functions of the other state variables as well as variables with their own dynamics (e.g., to create internal “micro-stimuli”).
12. a major thing that the mind does is to sculpt and manage its state representation. it discovers a) options and option models that induce useful abstract state variables and predictive world models, and b) useful non-linear, non-predictive state variables. it continually assesses all state variables for utility, relevance, and the extent to which they generalize. researching the process of discovery is difficult outside of the context of a complete agent.
13. learning itself is intrinsically rewarding. the tradeoff between exploration and exploitation always comes down to “learning feels good.”
14. options are not data structures, and are not executed. they may exist only as abstractions.

some of these principles are stated in radical, absolutist, and reductionist terms. this is as it should be. in some cases, softer versions of the principles (for example, removing the word “all”) are still interesting. moreover, the words “is” and “are” in the principles are a shorthand and simplification. they should be interpreted in the sense of Marrʼs “levels of explanation of a complex information-processing system.” that is, “is” can be read as “is well thought of as” or “insight can be gained by thinking of it as.”

a complete agent can be obtained from just two processes:

• a moment-by-moment state-update process, and
• a moment-by-moment action selection policy.

everything else has an effect only by changing these two. a lot can be done purely by learning processes (operating uniformly as in principle 10), before introducing planning. this can be done in the following stages:

• (a) a policy and value function can be learned by conventional model-free reinforcement learning using the current state variables
• (b) state variables with a predictive interpretation can learn to become more accurate predictors
• (c) discovery processes can operate to find more useful predictive and non-predictive state variables
• (d) prediction of outcomes, together with fast learning, can produce a simple form of foresight and behavior controlled by anticipated consequences

much of the learning above constitutes learning a predictive world model, but it is not yet planning. planning requires learning from anticipated experience at states other than the current one. the agent must disassociate himself from the current state and imagine absent others.

The Definition of Intelligence

July 9, 2016

John McCarthy long ago gave one of the best definitions: "Intelligence is the computational part of the ability to achieve goals in the world”. That is pretty straightforward and does not require a lot of explanation. It also allows for intelligence to be a matter of degree, and for intelligence to be of several varieties, which is as it should be. Thus a person, a thermostat, a chess-playing program, and a corporation all achieve goals to various degrees and in various senses. For those looking for some ultimate ‘true intelligence’, the lack of an absolute, binary definition is disappointing, but that is also as it should be.

The part that might benefit from explanation is what it means to achieve goals. What does it mean to have a goal? How can I tell if a system really has a goal rather than seems to? These questions seem deep and confusing until you realize that a system having a goal or not, despite the language, is not really a property of the system itself. It is in the relationship between the system and an observer. (In Dennett's words, it is a ‘stance’ that the observer take with respect to the system.)

What is it in the relationship between the system and the observer that makes it a goal-seeking system? It is that the system is most usefully understood (predicted, controlled) in terms of its outcomes rather than its mechanisms. Thus, for a home-owner a thermostat is most usefully understood in terms of its keeping the temperature constant, as achieving that outcome, as having that goal. But if i am an engineer designing a thermostat, or a repairman fixing one, then i need to understand it at a mechanistic level—and thus it does not have a goal. The thermostat does or does not have a goal depending of the observer. Another example is the person playing the chess computer. If I am a naive person, and a weaker player, I can best understand the computer as having the goal of beating me, of checkmating my king. But if I wrote the chess program (and it does not look very deep) I have a mechanistic way of understanding it that may be more useful for predicting and controlling it (and beating it).

Putting these two together, we can define intelligence concisely (though without much hope of being genuinely understood without further explanation):

Intelligence is the computational part of the ability to achieve goals. A goal achieving system is one that is more usefully understood in terms of outcomes than in terms of mechanisms.

The Bitter Lesson

Source March 13, 2019

The biggest lesson that can be read from 70 years of AI research is that general methods that leverage computation are ultimately the most effective, and by a large margin. The ultimate reason for this is Moore's law, or rather its generalization of continued exponentially falling cost per unit of computation. Most AI research has been conducted as if the computation available to the agent were constant (in which case leveraging human knowledge would be one of the only ways to improve performance) but, over a slightly longer time than a typical research project, massively more computation inevitably becomes available. Seeking an improvement that makes a difference in the shorter term, researchers seek to leverage their human knowledge of the domain, but the only thing that matters in the long run is the leveraging of computation. These two need not run counter to each other, but in practice they tend to. Time spent on one is time not spent on the other. There are psychological commitments to investment in one approach or the other. And the human-knowledge approach tends to complicate methods in ways that make them less suited to taking advantage of general methods leveraging computation. There were many examples of AI researchers' belated learning of this bitter lesson, and it is instructive to review some of the most prominent.

In computer chess, the methods that defeated the world champion, Kasparov, in 1997, were based on massive, deep search. At the time, this was looked upon with dismay by the majority of computer-chess researchers who had pursued methods that leveraged human understanding of the special structure of chess. When a simpler, search-based approach with special hardware and software proved vastly more effective, these human-knowledge-based chess researchers were not good losers. They said that "brute force" search may have won this time, but it was not a general strategy, and anyway it was not how people played chess. These researchers wanted methods based on human input to win and were disappointed when they did not.

A similar pattern of research progress was seen in computer Go, only delayed by a further 20 years. Enormous initial efforts went into avoiding search by taking advantage of human knowledge, or of the special features of the game, but all those efforts proved irrelevant, or worse, once search was applied effectively at scale. Also important was the use of learning by self play to learn a value function (as it was in many other games and even in chess, although learning did not play a big role in the 1997 program that first beat a world champion). Learning by self play, and learning in general, is like search in that it enables massive computation to be brought to bear. Search and learning are the two most important classes of techniques for utilizing massive amounts of computation in AI research. In computer Go, as in computer chess, researchers' initial effort was directed towards utilizing human understanding (so that less search was needed) and only much later was much greater success had by embracing search and learning.

In speech recognition, there was an early competition, sponsored by DARPA, in the 1970s. Entrants included a host of special methods that took advantage of human knowledge---knowledge of words, of phonemes, of the human vocal tract, etc. On the other side were newer methods that were more statistical in nature and did much more computation, based on hidden Markov models (HMMs). Again, the statistical methods won out over the human-knowledge-based methods. This led to a major change in all of natural language processing, gradually over decades, where statistics and computation came to dominate the field. The recent rise of deep learning in speech recognition is the most recent step in this consistent direction. Deep learning methods rely even less on human knowledge, and use even more computation, together with learning on huge training sets, to produce dramatically better speech recognition systems. As in the games, researchers always tried to make systems that worked the way the researchers thought their own minds worked---they tried to put that knowledge in their systems---but it proved ultimately counterproductive, and a colossal waste of researcher's time, when, through Moore's law, massive computation became available and a means was found to put it to good use.

In computer vision, there has been a similar pattern. Early methods conceived of vision as searching for edges, or generalized cylinders, or in terms of SIFT features. But today all this is discarded. Modern deep-learning neural networks use only the notions of convolution and certain kinds of invariances, and perform much better.

This is a big lesson. As a field, we still have not thoroughly learned it, as we are continuing to make the same kind of mistakes. To see this, and to effectively resist it, we have to understand the appeal of these mistakes. We have to learn the bitter lesson that building in how we think we think does not work in the long run. The bitter lesson is based on the historical observations that 1) AI researchers have often tried to build knowledge into their agents, 2) this always helps in the short term, and is personally satisfying to the researcher, but 3) in the long run it plateaus and even inhibits further progress, and 4) breakthrough progress eventually arrives by an opposing approach based on scaling computation by search and learning. The eventual success is tinged with bitterness, and often incompletely digested, because it is success over a favored, human-centric approach.

One thing that should be learned from the bitter lesson is the great power of general purpose methods, of methods that continue to scale with increased computation even as the available computation becomes very great. The two methods that seem to scale arbitrarily in this way are search and learning.

The second general point to be learned from the bitter lesson is that the actual contents of minds are tremendously, irredeemably complex; we should stop trying to find simple ways to think about the contents of minds, such as simple ways to think about space, objects, multiple agents, or symmetries. All these are part of the arbitrary, intrinsically-complex, outside world. They are not what should be built in, as their complexity is endless; instead we should build in only the meta-methods that can find and capture this arbitrary complexity. Essential to these methods is that they can find good approximations, but the search for them should be by our methods, not by us. We want AI agents that can discover like we can, not which contain what we have discovered. Building in our discoveries only makes it harder to see how the discovering process can be done.

Machine Learning DevOps

Machine learning models make predictions for new data based on the data they have been trained on. It is essential that the data is clean, correct, and safe to use without any privacy or bias issues. Real-world data can also continuously change, so inputs and predictions have to be monitored for any shifts that may be problematic for the model. These are complex challenges that are distinct from those found in traditional DevOps.

• Motivation

DevOps practices are centred on the “build and release” process and continuous integration. Traditional development builds are packages of executable artifacts compiled from source code. Non-code supporting data in these builds tends to be limited to relatively small static config files. In essence, traditional DevOps is geared to building programs consisting of sets of explicitly defined rules that give specific outputs in response to specific inputs.

In contrast, machine-learning models make predictions by indirectly capturing patterns from data, not by formulating all the rules. A characteristic machine-learning problem involves making new predictions based on known data. Machine-learning builds run a pipeline that extracts patterns from data and creates a weighted machine-learning model artifact. This makes these builds far more complex and the whole data science workflow more experimental. As a result, a key part of the MLOps challenge is supporting multi-step machine learning model builds that involve large data volumes and varying parameters.

To run projects safely in live environments, we need to be able to monitor for problem situations and see how to fix things when they go wrong. There are pretty standard DevOps practices for how to record code builds in order to go back to old versions. But MLOps does not yet have standardisation on how to record and go back to the data that was used to train a version of a model.

There are also special MLOps challenges to face in the live environment. There are largely agreed DevOps approaches for monitoring for error codes or an increase in latency. But it’s a different challenge to monitor for bad predictions. You may not have any direct way of knowing whether a prediction is good, and may have to instead monitor indirect signals such as customer behaviour. It can also be hard to know in advance how well your training data represents your live data. For example, it might match well at a general level but there could be specific kinds of exceptions. This risk can be mitigated with careful monitoring and cautious management of the rollout of new versions.

• Tool landscape

The effort involved in solving MLOps challenges can be reduced by leveraging a platform and applying it to the particular case. Many organisations face a choice of whether to use an off-the-shelf machine-learning platform or try to put an in-house platform together themselves by assembling open-source components. Some machine-learning platforms are part of a cloud provider’s offering. This may or may not appeal, depending on the cloud strategy of the organisation. Other platforms are not cloud-specific and instead offer self-install or a custom hosted solution. Instead of choosing a platform, organisations can instead choose to assemble their own. This may be a preferred route when requirements are too niche to fit a current platform, such as needing integrations to other in-house systems or if data has to be stored in a particular location or format. Choosing to assemble an in-house platform requires learning to navigate the ML tool landscape. This landscape is complex with different tools specialising in different niches and in some cases there are competing tools approaching similar problems in different ways.

• Governance

Challenges around reproducibility and monitoring of machine learning systems are governance problems. For many projects these are not the only challenges as customers might reasonably expect to be able to ask why a prediction concerning them was made. Explainability is a data science problem in itself. Modelling techniques can be divided into “black-box” and “white-box”, depending on whether the method can naturally be inspected to provide insight into the reasons for particular predictions. With black-box models, such as proprietary neural networks, the options for interpreting results are more restricted and more difficult to use than the options for interpreting a white-box linear model. In highly regulated industries, it can be impossible for AI projects to move forward without supporting explainability. For example, medical diagnosis systems may need to be highly interpretable so that they can be investigated when things go wrong or so that the model can aid a human doctor. This can mean that projects are restricted to working with models that admit of acceptable interpretability. Making black-box models more interpretable is a fast-growth area, with new techniques rapidly becoming available.

• Product teams, CI/CD, automated testing and IT are working closely with the business. However, where are your data scientists and ML engineers? Bring them closer as well - but there is no need to call it DevMLOps, ok?

• Data scientists usually come from an academic background and are afraid of sharing models that they do not consider good enough - create a safe environment for them to fail!

• Continuous integration and continuous deployment (CI/CD) are amazing best practices that can also be applied to machine learning components.

• More than CI/CD, we should do continuous evaluation of the models - version algorithms, parameters, data and its results.

• Machine learning bugs are not just functions returning wrong values, they can cause bias, accuracy drift, and model fragility.

• The fact that machine learning development focuses on hyperparameter tuning and data pipelines does not mean that we need to reinvent the wheel or look for a completely new way. DevOps lays a strong foundation which Data science practitioners must also absorb a lot of the industry gains from the last year, a direct result of the DevOps culture:

  • culture change to support experimentation, experimentation/failure in its core,
  • continuous evaluation,
  • deployable artifacts,
  • a sharing culture,
  • abstraction layers,
  • observability, and
  • working in products and services.

• What are the challenges that come with artificial intelligence and machine learning regarding integrating with development and deployment?

They are the same problems that we solved for traditional development but with a different perspective now: version control, packaging, deployment, collaboration and serving. The main issue is that we are trying to force the solutions we used before in software development, into this ecosystem. In the last year, we saw a significant increase in the number of products (especially Open Source) trying to solve ML's development lifecycle - Spark runs on top of Kubernetes, tensorflow, kubeflow, MLflow, Uber's Michelangelo, and cloud providers giving tools that allow the training and serving of models. We are witnessing the maturation of this ecosystem, and it's a growing environment.

• What about bugs and testing... how does that work with ML components?

Concerning the bugs it is important to keep notice of machine learning bugs: Bias, Drift and Fragility.

Bias comes from the bias that exists on the datasets used to build the feature and can have catastrophic results, especially when used on blackbox-like models. Cathy O'Neil's Weapons of Math Destruction is a book from 2016 that raised a lot of these problems in algorithms making important decisions concerning hiring, classifying people and others.

Drift occurs when models are built, working well and deployed. You may consider the job over and nothing else is needed, right? Unfortunately not. The model must be recalibrated and resynced according to the usage and data to keep the accuracy. Otherwise, it will drift and become worse with time.

Fragility is related to bias, but more related to changes outside of the team's reach. A change in definition, data that becomes unavailable, a null value that should not be there… how can your model cope with these issues, how fragile is it?

The worst part is, the majority of these bugs in ML cannot be identified before production. That is why monitoring and observability, others pillars from DevOps, play a gigantic role in machine learning components. You must measure proxies that identify the business value that your ML components should impact. For example, have you created a recommendation engine, and are you applying an AB test strategy to roll-out? You cannot directly track ML components, but you may be able to analyze proxy measures on it. These types of metrics and focusing on measuring can help you to detect and approach the ML bugs early on: bias, drift, and fragility.

• Distance between data science and operations. What is causing this distance?

The same problem that affected (and still does) the business world and "gave birth" to the DevOps movement - a distance between the business and the actual industrialization/operationalization of what is built.

This gap is a result of three things:

• slowness (things flowing from idea to production taking a gigantic time),

• lots of handovers (X talks to client, A writes the user story, B builds, C validates, D approves, E deploys, F operates, G fixes bugs, H rebuilds,...),

• and clustered teams working on projects, not products.

• What can we do to decrease distances and improve collaboration?

The hardest thing that any organization can do: change the culture.

In the case of ML engineers and data scientists, some cultural aspects can impact a lot, but the most compelling one I have seen is related to the background of the professionals. The majority of them have a very academic background, meaning that they are used to spending long periods working on one problem until it is good enough to be accepted in a publication. The bar there, to be good enough, is extremely high, not just on some metrics but also on the design of the experiments, mathematical rigor, and so on. In a business context this is important, but less so... That means that it is OK to publish a model with 60% accuracy and have it on a deployable state. It is better to have that ready and consider putting it in production today, than waiting months to have something "good enough". Maybe in three months that will not be a problem worth solving anymore. Moving fast with flexible possibilities is the best way to go.

• What’s your advice for companies who want to reap the benefits from applying artificial intelligence and machine learning? What should they do or not do?

Some cultural characteristics I have seen that support a short time-to-market and where a lot of value is generated from data science include:

• Data science: the "science" part indicates experimentation and failed tryouts. Not all experiments succeed, so data science will not produce mind-blowing solutions at all times. Sometimes you can go into a rabbit hole. Alternatively, the business may change. If you are a data scientist working on a project for a few days and you see no future in it, do you have the courage and autonomy to tell that to your boss/stakeholders? Likewise, the other way around... can they come to you at any time and say that the business changed and we must pivot?

• More than CI/CD, we need to talk about CE - continuous evaluation. Every time a new model is tested - it can be new hyperparameters in the same algorithm or a completely new algorithm - we must be able to compare it with previous runs. How accurate was it? Why the result different? Are we using the same dataset?

• Share not only your good models, but also the ones that are a total flunk! Version control your code and your models, at all times! Learn to use git at every moment! Why? Because when someone else sees that, they will not try it again with the same datasets and parameters... stop the waste!

• Provide platforms and tools for the data science to abstract the things they do not know (and they do not need to know). A data scientist may not know if they want to serve their models in REST or gRPC, how to package the model, if it should be deployed on the Kubernetes cluster or how many requests per second it should withstand - this is not their expertise. A team must provide a platform and a have a pipeline to do that and let the decisions be taken, experimented with and changed. Every company has its flow, ways of working and ideas... do not bend the culture to the tool.

• Work on products and services, not projects. Developers, security specialists, SRE's... everyone should be involved and help. By doing this, you can make sure that you have deployable artifacts from day one! After it is deployed, the job is not over... You have to operate, monitor, refactor, calibrate and do several things with ML models that are running on production.

Programming Language Theory and Practice

• Lambda Calculus
• Category Theory
• Type Systems
  • Dependent Types
• Homoiconicity
• Functional Programming
• Object Oriented Programming
• Domain Specific Languages
• Implementation
• Virtual Machines
• LLVM
• JIT
• Garbage Collection
• Parsing
• Language Server Protocol
• Incremental Compilation

Lambda Calculus

Category Theory

Type Systems

Dependent Types

Homoiconicity

Functional Programming

Object Oriented Programming

Domain Specific Languages

• 2015/05 Domain-Specific Languages vs. Notation
• 2017/03 How to write a DSL (in Python with Lark)
• 2018/07 Designing good DSL
• 2019/05 DSLs for non-programmers are a hoax
• 2020/04 The Power of Tiny DSLs

Implementation

Virtual Machines

LLVM

JIT

Garbage Collection

• The Garbage Collection Handbook
• Boehm: A garbage collector for C and C++
• Writing a Simple Garbage Collector in C
• 2012/12 Garbage collection thoughts
• 2013/09 A tour of V8: Garbage Collection
• 2013/12 Baby’s First Garbage Collector
• 2014/11 Exploring ARC
• 2015/04 ARC In Depth: Part I
• 2015/06 ARC In Depth: Part II
• 2015/04 Building a lower-latency GC
• 2015/07 A Well Known But Forgotten Trick: Object Pooling
• 2016/02 A toy generational garbage collector
• 2016/04 Malloc Envy
• 2016/09 Under the Hood - Performance Considerations of a Garbage Collector
• 2017/12 A Beginner’s Guide to Garbage Collection
• 2018/11 Garbage Collection is a Hack
• 2018/11 Common Mistakes about Generational Garbage Collection
• 2019/05 For Better Computing, Liberate CPUs From Garbage Collection
• 2019/12 Deciding when to collect garbage
• 2020/03 An in-depth Look at OCaml’s new “Best-fit” Garbage Collector Strategy
• 2021/02 The Trouble with Reference Counting
• 2021/09 .NET CLR Garbage Collection
• 2022/02 Dumpster diving the Go garbage collector

Parsing

Language Server Protocol

• Language Server Protocol
• GitHub - sourcegraph/emacs-lsp: LSP support for Emacs
• 2017/02 Why You Should Know the Language Server Protocol
• 2017/04 Language Server Protocol: A Language Server For DOT With Visual Studio Code
• 2018/05 Extending a client with the language server protocol
• 2019/03 r/ A LSP client maintainer's view of the LSP protocol.

Incremental Compilation

Books

• Programming Language Theory and Design
• Compilers
  • Practical Foundations for Programming Languages
  • Essentials of Programming Languages
  • Design Concepts in Programming Languages
  • Concepts, Techniques and Models of Computer Programming
  • Concepts of Programming Languages
  • Concepts in Programming Languages
  • Programming Language Concepts
  • Programming Language Pragmatics
  • Programming Languages and Operational Semantics: An Introduction
  • The Formal Semantics of Programming Languages: An Introduction
  • Types and Programming Languages
  • Advanced Topics in Types and Programming Languages
  • An Introduction to Functional Programming Through Lambda Calculus
  • Lambda Calculus with Types
  • Lambda-calculus, Combinators and Functional Programming
  • Type Theory and Formal Proof: An Introduction
  • Engineering A Compiler
    • 3rd Ed, 2022
    • 2nd Ed, 2011
  • Crafting Interpreters
  • Introduction to Compilers and Language Design
  • Compiling to Assembly from Scratch
  • Writing {An Interpreter, A Compiler} In Go
  • Modern Compiler Design
  • Implementing Programming Languages. An Introduction to Compilers and Interpreters
  • Language Implementation Patterns
  • Writing Compilers and Interpreters: A Software Engineering Approach
  • Compiler Design. Theory, Tools, Examples
  • Basics of Compiler Design
  • Compilers. Principles, Techniques and Tools
  • Optimizing Compilers for Modern Architectures
  • Compiler Design Handbook. Optimizations and Machine Code Generation
  • The Optimal Implementation of Functional Programming Languages
  • Modern Compiler Implementation in C
  • Modern Compiler Implementation in ML
  • Modern Compiler Implementation in Java
  • Building an Optimizing Compiler
  • Compiler Construction (Wirth)
  • Compiler Construction (Waite, Goos)
  • Let's Build a Compiler
  • The Functional Treatment of Parsing
  • Parsing Techniques. A Practical Guide
  • Compiler Design in C
  • The Implementation of Functional Programming Languages
  • The Design and Construction of Compilers
  • Writing Interactive Compilers and Interpreters
  • Assemblers, Compilers, and Program Translation
  • Compiler Construction: An Advanced Course
  • The Theory of Parsing, Translation, and Compiling
    • Volume 1 Parsing
    • Volume 2 Compiling

Programming Language Theory and Design

Compilers

Practical Foundations for Programming Languages

2nd Ed, 2016, Robert Harper

• Homepage

Types are the central organizing principle of the theory of programming languages. In this innovative book, Professor Robert Harper offers a fresh perspective on the fundamentals of these languages through the use of type theory. Whereas most textbooks on the subject emphasize taxonomy, Harper instead emphasizes genetics, examining the building blocks from which all programming languages are constructed. Language features are manifestations of type structure. The syntax of a language is governed by the constructs that define its types, and its semantics is determined by the interactions among those constructs. The soundness of a language design – the absence of ill-defined programs – follows naturally. Professor Harper's presentation is simultaneously rigorous and intuitive, relying on only elementary mathematics. The framework he outlines scales easily to a rich variety of language concepts and is directly applicable to their implementation. The result is a lucid introduction to programming theory that is both accessible and practical.

Essentials of Programming Languages

2012, Friedman

A new edition of a textbook that provides students with a deep, working understanding of the essential concepts of programming languages, completely revised, with significant new material. This book provides students with a deep, working understanding of the essential concepts of programming languages. Most of these essentials relate to the semantics, or meaning, of program elements, and the text uses interpreters (short programs that directly analyze an abstract representation of the program text) to express the semantics of many essential language elements in a way that is both clear and executable. The approach is both analytical and hands-on. The book provides views of programming languages using widely varying levels of abstraction, maintaining a clear connection between the high-level and low-level views. Exercises are a vital part of the text and are scattered throughout; the text explains the key concepts, and the exercises explore alternative designs and other issues. The complete Scheme code for all the interpreters and analyzers in the book can be found online through The MIT Press web site. For this new edition, each chapter has been revised and many new exercises have been added. Significant additions have been made to the text, including completely new chapters on modules and continuation-passing style. Essentials of Programming Languages can be used for both graduate and undergraduate courses, and for continuing education courses for programmers.

Design Concepts in Programming Languages

2008, Turbak

Key ideas in programming language design and implementation explained using a simple and concise framework; a comprehensive introduction suitable for use as a textbook or a reference for researchers.

Hundreds of programming languages are in use today--scripting languages for Internet commerce, user interface programming tools, spreadsheet macros, page format specification languages, and many others. Designing a programming language is a metaprogramming activity that bears certain similarities to programming in a regular language, with clarity and simplicity even more important than in ordinary programming. This comprehensive text uses a simple and concise framework to teach key ideas in programming language design and implementation.

The book's unique approach is based on a family of syntactically simple pedagogical languages that allow students to explore programming language concepts systematically. It takes as premise and starting point the idea that when language behaviors become incredibly complex, the description of the behaviors must be incredibly simple. The book presents a set of tools (a mathematical metalanguage, abstract syntax, operational and denotational semantics) and uses it to explore a comprehensive set of programming language design dimensions, including dynamic semantics (naming, state, control, data), static semantics (types, type reconstruction, polymporphism, effects), and pragmatics (compilation, garbage collection).

The many examples and exercises offer students opportunities to apply the foundational ideas explained in the text. Specialized topics and code that implements many of the algorithms and compilation methods in the book can be found on the book's Web site, along with such additional material as a section on concurrency and proofs of the theorems in the text. The book is suitable as a text for an introductory graduate or advanced undergraduate programming languages course; it can also serve as a reference for researchers and practitioners.

Concepts, Techniques and Models of Computer Programming

2004, Van Roy

• Table of Contents
  • 1 Introduction to Programming Concepts
  • Part I General Computation Models
    • 2 Declarative Computation Model
    • 3 Declarative Programming Techniques
    • 4 Declarative Concurrency
    • 5 Message-Passing Concurrency
    • 6 Explicit State
    • 7 Object-Oriented Programming
    • 8 Shared-State Concurrency
    • 9 Relational Programming
  • Part II Specialized Computation Models
    • 10 Graphical User Interface Programming
    • 11 Distributed Programming
    • 12 Constraint Programming
  • Part III Semantics
    • 13 Language Semantics
  • Part IV Appendixes
    • A Mozart System Development Environment
    • B Basic Data Types
    • C Language Syntax
    • D General Computation Model

Teaching the science and the technology of programming as a unified discipline that shows the deep relationships between programming paradigms.

This innovative text presents computer programming as a unified discipline in a way that is both practical and scientifically sound. The book focuses on techniques of lasting value and explains them precisely in terms of a simple abstract machine. The book presents all major programming paradigms in a uniform framework that shows their deep relationships and how and where to use them together. After an introduction to programming concepts, the book presents both well-known and lesser-known computation models (programming paradigms). Each model has its own set of techniques and each is included on the basis of its usefulness in practice. The general models include declarative programming, declarative concurrency, message-passing concurrency, explicit state, object-oriented programming, shared-state concurrency, and relational programming. Specialized models include graphical user interface programming, distributed programming, and constraint programming. Each model is based on its kernel language--a simple core language that consists of a small number of programmer-significant elements. The kernel languages are introduced progressively, adding concepts one by one, thus showing the deep relationships between different models. The kernel languages are defined precisely in terms of a simple abstract machine. Because a wide variety of languages and programming paradigms can be modeled by a small set of closely related kernel languages, this approach allows programmer and student to grasp the underlying unity of programming. The book has many program fragments and exercises, all of which can be run on the Mozart Programming System, an Open Source software package that features an interactive incremental development environment.

Concepts of Programming Languages

2016, Sebesta

Concepts of Computer Programming Languages introduces students to the fundamental concepts of computer programming languages and provides them with the tools necessary to evaluate contemporary and future languages. An in-depth discussion of programming language structures, such as syntax and lexical and syntactic analysis, also prepares readers to study compiler design. The Eleventh Edition maintains an up-to-date discussion on the topic with the removal of outdated languages such as Ada and Fortran. The addition of relevant new topics and examples such as reflection and exception handling in Python and Ruby add to the currency of the text. Through a critical analysis of design issues of various program languages, Concepts of Computer Programming Languages teaches programmers the essential differences between computing with specific languages.

Concepts in Programming Languages

2010, Mitchell

For undergraduate and beginning graduate students, this textbook explains and examines the central concepts used in modern programming languages, such as functions, types, memory management, and control. The book is unique in its comprehensive presentation and comparison of major object-oriented programming languages. Separate chapters examine the history of objects, Simula and Smalltalk, and the prominent languages C++ and Java. The author presents foundational topics, such as lambda calculus and denotational semantics, in an easy-to-read, informal style, focusing on the main insights provided by these theories. Advanced topics include concurrency, concurrent object-oriented programming, program components, and inter-language interoperability. A chapter on logic programming illustrates the importance of specialized programming methods for certain kinds of problems. This book will give the reader a better understanding of the issues and tradeoffs that arise in programming language design, and a better appreciation of the advantages and pitfalls of the programming languages they use.

Programming Language Concepts

1997, Ghezzi

Programming Language Pragmatics

2015, Scott

Programming Language Pragmatics, Fourth Edition, is the most comprehensive programming language textbook available today. It is distinguished and acclaimed for its integrated treatment of language design and implementation, with an emphasis on the fundamental tradeoffs that continue to drive software development.

The book provides readers with a solid foundation in the syntax, semantics, and pragmatics of the full range of programming languages, from traditional languages like C to the latest in functional, scripting, and object-oriented programming. This fourth edition has been heavily revised throughout, with expanded coverage of type systems and functional programming, a unified treatment of polymorphism, highlights of the newest language standards, and examples featuring the ARM and x86 64-bit architectures.

--

Programming Languages and Operational Semantics: An Introduction

2004, Fernandez

This book provides a concise introduction to the essential concepts in programming languages, using techniques from operational semantics. It is addressed to undergraduate students, as a complement to programming languages or operational semantics courses. There are three parts in the book, highlighting three major programming paradigms: - imperative languages: the main features of these languages are illustrated using Java, C, Pascal - functional languages: modern languages such as ML and Haskell are used to describe the functional style of programming - logic languages: the last part of the book gives an overview of logic programming using Prolog. After a general description of each family of languages, their semantics are studied using abstract machines and structural operational semantics. The book gives an in-depth analysis of the basic concepts in programming languages instead of a mere survey of languages, privileging the understanding of the basic techniques underlying the semantics of languages over simply describing their properties.

The Formal Semantics of Programming Languages: An Introduction

1993, Winskel

The Formal Semantics of Programming Languages provides the basic mathematical techniques necessary for those who are beginning a study of the semantics and logics of programming languages. These techniques will allow students to invent, formalize, and justify rules with which to reason about a variety of programming languages. Although the treatment is elementary, several of the topics covered are drawn from recent research, including the vital area of concurency. The book contains many exercises ranging from simple to miniprojects.Starting with basic set theory, structural operational semantics is introduced as a way to define the meaning of programming languages along with associated proof techniques. Denotational and axiomatic semantics are illustrated on a simple language of while-programs, and fall proofs are given of the equivalence of the operational and denotational semantics and soundness and relative completeness of the axiomatic semantics. A proof of Godel's incompleteness theorem, which emphasizes the impossibility of achieving a fully complete axiomatic semantics, is included. It is supported by an appendix providing an introduction to the theory of computability based on while-programs. Following a presentation of domain theory, the semantics and methods of proof for several functional languages are treated. The simplest language is that of recursion equations with both call-by-value and call-by-name evaluation. This work is extended to lan guages with higher and recursive types, including a treatment of the eager and lazy lambda-calculi. Throughout, the relationship between denotational and operational semantics is stressed, and the proofs of the correspondence between the operation and denotational semantics are provided. The treatment of recursive types - one of the more advanced parts of the book - relies on the use of information systems to represent domains. The book concludes with a chapter on parallel programming languages, accompanied by a discussion of methods for specifying and verifying nondeterministic and parallel programs.

Types and Programming Languages

2020, Benjamin Pierce

A comprehensive introduction to type systems and programming languages. A type system is a syntactic method for automatically checking the absence of certain erroneous behaviors by classifying program phrases according to the kinds of values they compute. The study of type systems--and of programming languages from a type-theoretic perspective--has important applications in software engineering, language design, high-performance compilers, and security.

This text provides a comprehensive introduction both to type systems in computer science and to the basic theory of programming languages. The approach is pragmatic and operational; each new concept is motivated by programming examples and the more theoretical sections are driven by the needs of implementations. Each chapter is accompanied by numerous exercises and solutions, as well as a running implementation, available via the Web. Dependencies between chapters are explicitly identified, allowing readers to choose a variety of paths through the material.

The core topics include the untyped lambda-calculus, simple type systems, type reconstruction, universal and existential polymorphism, subtyping, bounded quantification, recursive types, kinds, and type operators. Extended case studies develop a variety of approaches to modeling the features of object-oriented languages.

Advanced Topics in Types and Programming Languages

2004, Benjamin Pierce

A thorough and accessible introduction to a range of key ideas in type systems for programming language.

The study of type systems for programming languages now touches many areas of computer science, from language design and implementation to software engineering, network security, databases, and analysis of concurrent and distributed systems. This book offers accessible introductions to key ideas in the field, with contributions by experts on each topic.

The topics covered include precise type analyses, which extend simple type systems to give them a better grip on the run time behavior of systems; type systems for low-level languages; applications of types to reasoning about computer programs; type theory as a framework for the design of sophisticated module systems; and advanced techniques in ML-style type inference.

Advanced Topics in Types and Programming Languages builds on Benjamin Pierce's Types and Programming Languages (MIT Press, 2002); most of the chapters should be accessible to readers familiar with basic notations and techniques of operational semantics and type systems--the material covered in the first half of the earlier book.

Advanced Topics in Types and Programming Languages can be used in the classroom and as a resource for professionals. Most chapters include exercises, ranging in difficulty from quick comprehension checks to challenging extensions, many with solutions.

An Introduction to Functional Programming Through Lambda Calculus

2011, Greg Michaelson

• Table of Contents
  • Preface
  • 1. Introduction
  • 2. Lambda Calculus
  • 3. Conditions, booleans, and numbers
  • 4. Recursion and arithmetic
  • 5. Types
  • 6. Lists and Strings
  • 7. Composite values and trees
  • 8. Evaluation
  • 9. Functional programming in Standard ML
  • 10. Functional programming and LISP

Functional programming is rooted in lambda calculus, which constitutes the world's smallest programming language. This well-respected text offers an accessible introduction to functional programming concepts and techniques for students of mathematics and computer science. The treatment is as nontechnical as possible, and it assumes no prior knowledge of mathematics or functional programming. Cogent examples illuminate the central ideas, and numerous exercises appear throughout the text, offering reinforcement of key concepts. All problems feature complete solutions.

Lambda Calculus with Types

2014, Henk Barendregt

This handbook with exercises reveals in formalisms, hitherto mainly used for hardware and software design and verification, unexpected mathematical beauty. The lambda calculus forms a prototype universal programming language, which in its untyped version is related to Lisp, and was treated in the first author's classic The Lambda Calculus (1984). The formalism has since been extended with types and used in functional programming (Haskell, Clean) and proof assistants (Coq, Isabelle, HOL), used in designing and verifying IT products and mathematical proofs. In this book, the authors focus on three classes of typing for lambda terms: simple types, recursive types and intersection types. It is in these three formalisms of terms and types that the unexpected mathematical beauty is revealed. The treatment is authoritative and comprehensive, complemented by an exhaustive bibliography, and numerous exercises are provided to deepen the readers' understanding and increase their confidence using types.

Lambda-calculus, Combinators and Functional Programming

2009, G. E. Revesz

Originally published in 1988, this book presents an introduction to lambda-calculus and combinators without getting lost in the details of mathematical aspects of their theory. Lambda-calculus is treated here as a functional language and its relevance to computer science is clearly demonstrated. The main purpose of the book is to provide computer science students and researchers with a firm background in lambda-calculus and combinators and show the applicabillity of these theories to functional programming. The presentation of the material is self-contained. It can be used as a primary text for a course on functional programming. It can also be used as a supplementary text for courses on the structure and implementation of programming languages, theory of computing, or semantics of programming languages.

Type Theory and Formal Proof: An Introduction

2016, Rob Nederpelt

Type theory is a fast-evolving field at the crossroads of logic, computer science and mathematics. This gentle step-by-step introduction is ideal for graduate students and researchers who need to understand the ins and outs of the mathematical machinery, the role of logical rules therein, the essential contribution of definitions and the decisive nature of well-structured proofs. The authors begin with untyped lambda calculus and proceed to several fundamental type systems, including the well-known and powerful Calculus of Constructions. The book also covers the essence of proof checking and proof development, and the use of dependent type theory to formalise mathematics. The only prerequisite is a basic knowledge of undergraduate mathematics. Carefully chosen examples illustrate the theory throughout. Each chapter ends with a summary of the content, some historical context, suggestions for further reading and a selection of exercises to help readers familiarise themselves with the material.

Engineering A Compiler

Cooper, Torczon

3rd Ed, 2022

Engineering a Compiler, Third Edition covers the latest developments in compiler technology, with new chapters focusing on semantic elaboration (the problems that arise in generating code from the ad-hoc syntax-directed translation schemes in a generated parser), on runtime support for naming and addressability, and on code shape for expressions, assignments and control-structures. Leading educators and researchers, Keith Cooper and Linda Torczon, have revised this popular text with a fresh approach to learning important techniques for constructing a modern compiler, combining basic principles with pragmatic insights from their own experience building state-of-the-art compilers.

2nd Ed, 2011

• Table of Contents

This entirely revised second edition of Engineering a Compiler is full of technical updates and new material covering the latest developments in compiler technology. In this comprehensive text you will learn important techniques for constructing a modern compiler. Leading educators and researchers Keith Cooper and Linda Torczon combine basic principles with pragmatic insights from their experience building state-of-the-art compilers. They will help you fully understand important techniques such as compilation of imperative and object-oriented languages, construction of static single assignment forms, instruction scheduling, and graph-coloring register allocation

Crafting Interpreters

2020, Bob Nystrom

• Homepage
• 2022/06 Crafting Interpreters: A Review HN

Introduction to Compilers and Language Design

2020, Douglas Thain

• Homepage L.rs

Compiling to Assembly from Scratch

2020, Vladimir Keleshev

• Homepage
• Github

Writing {An Interpreter, A Compiler} In Go

2018, Thorsten Ball

• Thorsten Ball: Writing An Interpreter In Go
• Thorsten Ball: Writing A Compiler In Go

Modern Compiler Design

2012, 2nd Ed, Grune

• Table of Contents
  • 1 Introduction
  • Part I
    • 2 Program Text to Tokens - Lexical Analysis
    • 3 Tokens to Syntax Tree - Syntax Analysis
  • Part II
    • 4 Annotating the Abstract Syntax Tree
    • 5 Manual Context Handling
  • Part III
    • 6 Interpretation
    • 7 Code Generation
    • 8 Assemblers, Disassemblers, Linkers and Loaders
    • 9 Optimization Techniques
  • Part IV Memory Management
    • 10 Explicit and Implicit Memory Management
  • Part V From Abstract Syntax Tree to Intermediate Code
    • 11 Imperative and Object-Oriented Programs
    • 12 Functional Programs
    • 13 Logic Programs
    • 14 Parallel and Distributed Programs

"Modern Compiler Design" makes the topic of compiler design more accessible by focusing on principles and techniques of wide application. By carefully distinguishing between the essential (material that has a high chance of being useful) and the incidental (material that will be of benefit only in exceptional cases) much useful information was packed in this comprehensive volume. The student who has finished this book can expect to understand the workings of and add to a language processor for each of the modern paradigms, and be able to read the literature on how to proceed. The first provides a firm basis, the second potential for growth.

Implementing Programming Languages. An Introduction to Compilers and Interpreters

2012, Ranta

• Table of Contents
  • 1 Compilation Phases
  • 2 Grammars
  • 3 Lexing and Parsing
  • 4 Type Checking
  • 5 Interpreters
  • 6 Code Generation
  • 7 Functional Programming Languages
  • 8 The Language Design Space
  • A BNFC Quick Reference
  • B Some JVM instructions
  • C Summary of the Assignments
  • D Further Reading

Implementing a programming language means bridging the gap from the programmer's high-level thinking to the machine's zeros and ones. If this is done in an efficient and reliable way, programmers can concentrate on the actual problems they have to solve, rather than on the details of machines. But understanding the whole chain from languages to machines is still an essential part of the training of any serious programmer. It will result in a more competent programmer, who will moreover be able to develop new languages. A new language is often the best way to solve a problem, and less difficult than it may sound. This book follows a theory-based practical approach, where theoretical models serve as blueprint for actual coding. The reader is guided to build compilers and interpreters in a well-understood and scalable way. The solutions are moreover portable to different implementation languages. Much of the actual code is automatically generated from a grammar of the language, by using the BNF Converter tool. The rest can be written in Haskell or Java, for which the book gives detailed guidance, but with some adaptation also in C, C++, C#, or OCaml, which are supported by the BNF Converter. The main focus of the book is on standard imperative and functional languages: a subset of C++ and a subset of Haskell are the source languages, and Java Virtual Machine is the main target. Simple Intel x86 native code compilation is shown to complete the chain from language to machine. The last chapter leaves the standard paths and explores the space of language design ranging from minimal Turing-complete languages to human-computer interaction in natural language.

Language Implementation Patterns

2010, Parr

• Table of Contents
  • Part I Getting Started with Parsing
    • 1 Language Applications Cracked Open
    • 2 Basic Parsing Patterns
    • 3 Enhanced Parsing Patterns
  • Part II Analyzing Languages
    • 4 Building Intermetiad Form Trees
    • 5 Walking and Rewriting Trees
    • 6 Tracking and Identifying Program Symbols
    • 7 Managing Symbol Tables for Data Aggregates
    • 8 Enforcing Static Typing Rules
  • Part III Building Interpreters
    • 9 Building high-Level Interpreters
    • 10 Building Bytecode Interpreters
  • Part IV Translating and Generating Languages
    • 11 Translating Computer Languages
    • 12 Generating DSLs with Templates
    • 13 Putting It All Together

Knowing how to create domain-specific languages (DSLs) can give you a huge productivity boost. Instead of writing code in a general-purpose programming language, you can first build a custom language tailored to make you efficient in a particular domain. The key is understanding the common patterns found across language implementations. "Language Design Patterns" identifies and condenses the most common design patterns, providing sample implementations of each. The pattern implementations use Java, but the patterns themselves are completely general. Some of the implementations use the well-known ANTLR parser generator, so readers will find this book an excellent source of ANTLR examples as well. But this book will benefit anyone interested in implementing languages, regardless of their tool of choice. Other language implementation books focus on compilers, which you rarely need in your daily life. Instead, "Language Design Patterns" shows you patterns you can use for all kinds of language applications. You'll learn to create configuration file readers, data readers, model-driven code generators, source-to-source translators, source analyzers, and interpreters. Each chapter groups related design patterns and, in each pattern, you'll get hands-on experience by building a complete sample implementation. By the time you finish the book, you'll know how to solve most common language implementation problems.

Writing Compilers and Interpreters: A Software Engineering Approach

2009, Mak, 3rd Ed

• Github
• Table of Contents
  • Chapter 1: Introduction
  • Chapter 2: Framework I: Compiler and Interpreter
  • Chapter 3: Scanning
  • Chapter 4: The Symbol Table
  • Chapter 5: Parsing Expressions and Assignment Statements
  • Chapter 6: Interpreting Expressions and Assignment Statements
  • Chapter 7: Parsing Control Statements
  • Chapter 8: Interpreting Control Statements
  • Chapter 9: Parsing Declarations
  • Chapter 10: Type Checking
  • Chapter 11: Parsing Programs, Procedures, and Functions
  • Chapter 12: Interpreting Pascal Programs
  • Chapter 13: An Interactive Source-Level Debugger
  • Chapter 14: Framework II: An Integrated Development Environment (IDE)
  • Chapter 15: Jasmin Assembly Language and Code Generation for the Java Virtual Machine
  • Chapter 16: Compiling Programs, Assignment Statements, and Expressions
  • Chapter 17: Compiling Procedure and Function Calls and String Operations
  • Chapter 18: Compiling Control Statements, Arrays, and Records
  • Chapter 19: Additional Topics

Long-awaited revision to a unique guide that covers both compilers and interpreters Revised, updated, and now focusing on Java instead of C++, this long-awaited, latest edition of this popular book teaches programmers and software engineering students how to write compilers and interpreters using Java. You?ll write compilers and interpreters as case studies, generating general assembly code for a Java Virtual Machine that takes advantage of the Java Collections Framework to shorten and simplify the code. In addition, coverage includes Java Collections Framework, UML modeling, object-oriented programming with design patterns, working with XML intermediate code, and more. From the Back Cover Master the skills you need to build your own compilers and interpreters Compilers and interpreters are very difficult programs to write, but modern software engineering tackles the complexity. Design patterns and other object-oriented programming techniques guide you to develop well-structured code in incremental, understandable steps. Apply what you learn in this book to succeed with any complex software project. You'll learn to:

• Use Java to develop scanners and parsers for programming languages
• Employ UML to model software components
• Manage symbol tables with the Java Collections Framework
• Use XML to represent the generated intermediate code
• Develop an interpreter to execute programs, including a powerful interactive source-level debugger
• Implement an integrated development environment (IDE) that animates the execution of programs
• Use the IDE's graphical user interface to set breakpoints and single-step programs statement by statement with mouse clicks
• Develop a code generator that emits object code for the Java Virtual Machine (JVM), and run the compiled code on multiple platforms

Compiler Design. Theory, Tools, Examples

2010, Bergmann Homepage

• Table of Contents
  • 1 Introduction
  • 2 Lexical Analysis
  • 3 Syntax Analysis
  • 4 Top-Down Parsing
  • 5 Bottom-Up Parsing
  • 6 Code Generation
  • 7 Optimization

Basics of Compiler Design

2010, Torben Mogensen Homepage

• Table of Contents
  • 1 Introduction
  • 2 Lexical Analysis
  • 3 Syntax Analysis
  • 4 Scopes and Symbol Tables
  • 5 Interpretation
  • 6 Type Checking
  • 7 Intermediate-Code Generation
  • 8 Machine Code Generation
  • 9 Register Allocation
  • 10 Function Calls
  • 11 Analysis and Optimization
  • 12 Memory Management
  • 13 Bootstrapping a Compiler

Compilers. Principles, Techniques and Tools

2006, 2nd Ed, Aho, Lam, Sethi, Ullman

• Table of Contents
  • 1 Introduction
    • 1.1 Language Processors
    • 1.2 The structure of a compiler
      • 1.2.1 Lexical analysis
      • 1.2.2 Syntax analysis
      • 1.2.3 Semantic analysis
      • 1.2.4 Intermediate code generation
      • 1.2.4 Code optimization
      • 1.2.6 Code generation
      • 1.2.7 Symbol-table management
      • 1.2.8 The grouping of phases into passes
      • 1.2.9 Compiler-construction tools
    • 1.3 The evolution of programming languages
  • 2 A simple syntax-directed translator
  • 3 Lexical analysis
  • 4 Syntax analysis
  • 5 Syntax-directed translation
  • 6 Intermediate code generation
  • 7 Run-time environments
    • Storage organization
      • Static versus dynamic storage allocation
    • Stack allocation of space
      • Activation trees
      • Activation records
      • Calling sequences
      • Variable-length data on the stack
    • Access to nonlocal data on the stack
      • Data access without nested procedures
      • Issues with nested procedures
      • A language with nested procedure declarations
      • Nesting depth
      • Access links
      • Manipulating access links
      • Displays
    • Heap management
      • The memory manager
      • The memory hierarchy of a computer
      • Locality in programs
        • Optimization using the memory hierarchy
      • Reducing fragmentation
        • Best-fit and next-fit object placement
        • Managing and coalescing free space
      • Manual deallocation requests
        • Problems with manual deallocation
        • Programming conventions and tools
    • Introduction to garbage collection
      • Design goals for garbage collection
        • Basic requirement: type safety
        • Performance metrics
      • Reachability
      • Reference counting garbage collection
    • Introduction to trace-based collection
      • A basic mark-and-sweep collector
      • Basic abstraction
      • Optimizing mark-and-sweep
      • Mark-and-compact garbage collection
      • Copying collectors
      • Comparing costs
    • Short-pause garbage collection
      • Incremental garbage collection
        • Precision of incremental collection
      • Incremental reachability analysis
        • Implementing write barriers
        • Combining incremental and copying techniques
      • Partial-collection basics
      • Generational garbage collection
      • The train algorithm
        • Remembered sets
        • Managing trains
        • Garbage collecting a car
        • Panic mode
    • Advance topics in garbage collection
      • Parallel and concurrent garbage collection
      • Partial object relocation
      • Conservative collection for unsafe languages
      • Weak references
    • Summary
  • 8 Code generation
    • Issues in the design of a code generator
      • Input to the code generator
      • The target program
      • Instruction selection
      • Register allocation
    • The target language
      • A simple target machine model
      • Program and instruction costs
    • Addresses in the target code
      • Static allocation
      • Stack allocation
      • Run-time addresses for names
    • Basic blocks and flow graphs
      • Basic blocks
      • Next-use information
      • Flow graphs
      • Representation of flow graphs
      • Loops
    • Optimization of basic blocks
      • The DAG representation of basic blocks
      • Finding local common subexpressions
      • Dead code elimination
      • The use of algebraic identities
      • Representation of array references
      • Pointer assignments and procedure calls
      • Reassembling basic blocks from DAGs
    • A simple code generator
      • Register and address descriptors
      • The code-generation algorithm
        • Machine instructions for copy statements
        • Ending the basic block
        • Managing register and address descriptors Design of the function getReg
    • Peephole optimization
      • Eliminating redundant loads and stores
      • Eliminating unreachable code
      • Flow-of-control optimizations
      • Algebraic simplification and reduction in strength
      • Use of machine idioms
    • Register allocation and assignment
      • Global register allocation
      • Usage counts
      • Register assignment for outer loops
      • Register allocation by graph coloring
    • Instruction selection by tree-rewriting
      • Tree-translation scheme
      • Code generation by tiling an input tree
      • Pattern matching by parsing
      • Routines for semantic checking
      • General tree matching
    • Code generation for expressions
      • Ershov numbers
      • Generating code from labeled expression trees
      • Evaluating expression with an insufficient supply of registers
    • Dynamic programming code-generation
      • Contiguous evaluation
      • The dynamic programming algorithm
    • Summary
  • 9 Machine-independent optimizations
  • 10 Instruction-level parallelism
  • 11 Optimizing for parallelism and locality
  • Appendix A A Complete front end
  • Appendix B Finding linearly independent solutions

Optimizing Compilers for Modern Architectures

2005, Allen, Kennedy

• Table of Contents
  • 1 Compiler Challenges for High-Performance Architectures
  • 2 Dependence: Theory and Practice
  • 3 Dependence Testing
  • 4 Preliminary Transformations
  • 5 Enhancing Fine-Grained Parallelism
  • 6 Creating Coarse-Graned Parallelism
  • 7 Control Dependence
  • 8 Compiler Improvement of Register Usage
  • 9 Cache Management
  • 10 Scheduling
  • 11 Interprocedural Analysis and Optimization
  • 12 Other Applications of Dependence
  • 13 Compiling Array Assignments
  • 14 Compiling High-Performance Fortran

Compiler Design Handbook. Optimizations and Machine Code Generation

2003, Srikant, Shankars

• Table of Contents
  • 1 Data Flow Analysis
  • 2 Automatic Generation of Code Optimizers from Formal Specifications
  • 3 Scalar Compiler Optimizations on the Single Static Assignment
  • 4 Profile-Guided Compiler Optimizations
  • 5 Shape Analysis and Applications
  • 6 Optimizations for Object-Oriented Languages
  • 7 Data Flow Testing
  • 8 Program Slicing
  • 9 Debuggers for Programming Languages
  • 10 Dependence Analysis and Parallelization Transformations
  • 11 Compilation for Distributed Memory Architectures
  • 12 Automatic Data Distribution
  • 13 Register Allocation
  • 14 Architecture Description Language for Retargetable Compilation
  • 15 Instruction Selection Using Tree Parsing
  • 16 Retargetable Very Long Instruction Word Compiler Framework
  • 17 Instruction Scheduling
  • 18 Software Pipelining
  • 19 Dynamic Compilation
  • 20 Compiling Safe Mobile Code
  • 21 Type Systems in Programming Languages
  • 22 Introduction to Operational Semantics

The Optimal Implementation of Functional Programming Languages

1999, Asperti, Guerrini

• Table of Contents
  • 1 Introduction
  • 2 Optimal Reduction
  • 3 The Full Algorithm
  • 4 Optimal Reductions and Linear Logic
  • 5 Redex Families and Optimality
  • 6 Paths
  • 7 Read-Back
  • 8 Other Translations in Sharing Graphs
  • 9 Safe Nodes
  • 10 Complexity
  • 11 Functional Programming
  • 12 The Bologna Optimal Higher-Order Machine

Modern Compiler Implementation in C

1998, Appel

• Table of Contents
  • Part I Fundamentals of Compilation
    • 1 Introduction
    • 2 Lexical Analysis
    • 3 Parsing
    • 4 Abstract Syntax
    • 5 Semantic Analysis
    • 6 Activation Records
    • 7 Translation to Intermediate Code
    • 8 Basic Blocks and Traces
    • 9 Instruction Selection
    • 10 Liveness Analysis
    • 11 Register Allocation
    • 12 Putting it All Together
  • Part II Advanced Topics
    • 13 Garbage Collection
    • 14 Object-Oriented Languages
    • 15 Functional Programming Languages
    • 16 Polymorphic Types
    • 17 Dataflow Analysis
    • 18 Loop Optimization
    • 19 Static Single Assignment Form
    • 20 Pipelining and Scheduling
    • 21 The Memory Hierarchy

Modern Compiler Implementation in ML

1998, Appel

• Table of Contents
  • Part I Fundamentals of Compilation
    • 1 Introduction
    • 2 Lexical Analysis
    • 3 Parsing
    • 4 Abstract Syntax
    • 5 Semantic Analysis
    • 6 Activation Records
    • 7 Translation to Intermediate Code
    • 8 Basic Blocks and Traces
    • 9 Instruction Selection
    • 10 Liveness Analysis
    • 11 Register Allocation
    • 12 Putting it All Together
  • Part II Advanced Topics
    • 13 Garbage Collection
    • 14 Object-Oriented Languages
    • 15 Functional Programming Languages
    • 16 Polymorphic Types
    • 17 Dataflow Analysis
    • 18 Loop Optimization
    • 19 Static Single Assignment Form
    • 20 Pipelining and Scheduling
    • 21 The Memory Hierarchy

Modern Compiler Implementation in Java

1998, Appel

Building an Optimizing Compiler

1997, Morgan

• Table of Contents
  • 1 Overview
  • 2 Compiler Structure
  • 3 Graphs
  • 4 Flow Graph
  • 5 Local Optimization
  • 6 Alias Analysis
  • 7 Static Single Assignment
  • 8 Dominator-Based Optimization
  • 9 Advanced Techniques
  • 10 Global Optimization
  • 11 Limiting Resources
  • 12 Scheduling and Rescheduling
  • 13 Register Allocation
  • 14 The Object Module
  • 15 Completion and Futures

Compiler Construction (Wirth)

1996, Wirth Homepage

• Table of Contents
  • 1 Introduction
  • 2 Language and Syntax
  • 3 Regular Languages
  • 4 Analysis of Context-Free Language
  • 5 Attributed Grammars and Semantics
  • 6 The Programming Language Oberon-0
  • 7 A Parser for Oberon-0
  • 8 Consideation of Context Specified by Declarations
  • 9 A RISC Architecture as a Target
  • 10 Expressions and Assignments
  • 11 Conditional and Repeated Statements and Boolean Expressions
  • 12 Procedures and the Concept of Locality
  • 13 Elementary Data Types
  • 14 Open Arrays, Pointers, and Procedure Types
  • 15 Modules and Separate Compilation
  • 16 Code Optimizations and the Frontend/Backend Structure

Compiler Construction (Waite, Goos)

1995, Waite, Goos

• Table of Contents
  • 1 Introduction and Overview
  • 2 Properties of Programming Languages
  • 3 Properties of Real and Abstract Machines
  • 4 Abstract Program Representation
  • 5 Elements of Formal Systems
  • 6 Lexical Analysis
  • 7 Parsing
  • 8 Attribute Grammars
  • 9 Semantic Analysis
  • 10 Code Generation
  • 11 Assembly
  • 12 Error Handling
  • 13 Optimization
  • 14 Implementation

Let's Build a Compiler

1995, Jack Crenshaw

• Homepage

The Functional Treatment of Parsing

1993, Leermakers

• Table of Contents
  • 1 Context-Free Grammars
  • 2 Bunch Notation
  • 3 Grammar Interpretations
  • 4 Recursive Descent
  • 5 Grammar Transformations
  • 6 Recursive Ascent
  • 7 Parse Forest
  • 8 Attribute Grammars
  • 9 LR Parsers
  • 10 Some Notes

Parsing Techniques. A Practical Guide

1990, Grune, Jacobs

• Table of Contents
  • 1 Introduction
    • Parsing as a craft
    • The approach used
    • Outline of the contents
    • The annotated bibliography
  • 2 Grammars as a generating device
    • Languages as infinite sets
    • Formal grammars
    • The Chomsky hierarchy of grammars and languages
    • VW grammars
    • Actually generating sentences from a grammar
    • To shrink or not to shrink
    • A characterization of the limits of CF and FS grammars
    • Hygiene in grammars
    • The semantic connection
    • A metaphorical comparison of grammar types
  • 3 Introduction to parsing
    • Various kinds of ambiguity
    • Linearization of the parse tree
    • Two ways to parse a sentence
    • Non-deterministic automata
    • Recognition and parsing gort type 0 to type 4 grammars
    • An overview of parsing methods
  • 4 General one-directional methods
    • Unger's parsing method
    • The CYK parsing method
  • 5 Regular grammars and finite state machines
    • Applications of regular grammars
    • Producing from a regular grammar
    • Parsing with a regular grammar
  • 6 General directional top-down methods
    • Imitating left'most productions
    • The pushdown automaton
    • Breadth-first top-down parsing
    • Eliminating left-recursion
    • Depth-first (backtracking) parsers
    • Recursive descent
    • Definite clause grammars
  • 7 General bottom-up parsing
    • Parsing by searching
    • Top-down restricted breadth-first bottom-up parsing
  • 8 Deterministic top-down methods
    • Replacing search by table look-up
    • LL(1) grammars
    • LL(k) grammars
    • Extended LL(1) grammars
  • 9 Deterministic bottom-up parsing
    • Simple handle-isolating techniques
    • Precedence parsing
    • Bounded-context parsing
    • LR methods
    • LR(1)
    • LALR(1) parsing
    • Further developments of LR methods
    • Tomita's parser
    • Non-canonical parsers
    • LR(k) as an ambiguity test
  • 10 Error handling
    • Detection versus recovery versus correction
    • Parsing techniques and error detection
    • Recovering from errors
    • Global error handling
    • Ad hoc methods
    • Regional error handling
    • Local error handling
    • Suffix parsing
  • 11 Comparative survey
    • Considerations
    • General parsers
    • Linear-time parsers
  • 12 A simple general context-free parser
    • Principles of the parser
    • The program
    • Parsing in polynomial time
  • 13 Annotated bibliography

Compiler Design in C

1990, Holub

• Table of Contents
  • 1 Basic Concepts
    • 1.1 The Parts of the Compiler
    • 1.2 Representing Computer Languages
    • 1.3 A Recursive-Descent Expression Compiler
  • 2 Input and Lexical Analysis
    • 2.1 The Lexical Analyzer as Part of a Compiler
    • 2.2 Error Recovery in Lexical Analysis
    • 2.3 Input Systems
    • 2.4 Lexical Analysis
    • 2.5 Lex - a Lexical-Analyzer Generator
  • 3 Context-Free Grammars
    • 3.1 Sentences, Phrases, and Context-Free Grammars
    • 3.2 Derivations and Sentential Forms
    • 3.3 Parse Trees and Semantic Difficulties
    • 3.4 Epsilon Productions
    • 3.5 The End-of-Input Marker
    • 3.6 Right-Linear Grammars
    • 3.7 Lists, Recursion, and Associativity
    • 3.8 Expressions
    • 3.9 Ambiguous Grammars
    • 3.10 Syntax-Directed Translation
    • 3.11 Representing Generic Grammars
  • 4 Top-Down Parsing
    • 4.1 Push-Down Automata
    • 4.2 Using a PDA for a Top-Down Parse
    • 4.3 Error Recovery in a Top-Down Parser
    • 4.4 Augmented Grammars and Table-Driven Parsers
    • 4.5 Automating the Top-Down Parse Process
    • 4.6 LL(1) Grammars and Their Limitations
    • 4.7 Making the Parse Tables
    • 4.8 Modifying Grammars
    • 4.9 Implementing LL(1) Grammars
    • 4.10 LLama - Implementing an LL(1) Parser-Generator
  • 5 Bottom-Up Parsing
    • 5.1 How Bottom-Up Parsing Works
    • 5.2 Recursion in Bottom-Up Parsing
    • 5.3 Implementing the Parser as a State Machine
    • 5.4 Error Recovery in an LR Parser
    • 5.5 The Value Stack and Attribute Processing
    • 5.6 Creating LR Parse Tables - Theory
    • 5.7 Representing LR State Tables
    • 5.8 Eliminating Single-Reduction States
    • 5.9 Using Ambiguous Grammars
    • 5.10 Implementing an LALR(1) Parser - The Occs Output File
    • 5.11 Implementing an LALR(1) Parser Generator - Occs Internals
    • 5.12 Parser-File Generation
    • 5.13 Generating LALR(1) Parse Tables
  • 6 Code Generation
    • 6.1 Intermediate Languages
    • 6.2 C-Code An Intermediate Language and Virtual Machine
    • 6.3 The Symbol Table
    • 6.4 The Parser: Configuration
    • 6.5 The Lexical Analyzer
    • 6.6 Declarations
    • 6.7 The gen() Subroutine
    • 6.8 Expressions
    • 6.8 Statements and Control Flow
  • 7 Optimization Strategies
    • 7.1 Parser Optimizations
    • 7.2 Linear (Peephole) Optimizations
    • 7.3 Structural Optimizations
    • 7.4 Aliasing Problems

The Implementation of Functional Programming Languages

1987, Peyton Jones

• Homepage
• Table of Contents
  • 1 Introduction
  • Part I Compiling High-Level Functional Languages
    • 2 The Lambda Calculus
    • 3 Translating a High-Level Functional Language into the Lambda Calculus
    • 4 Structured Types and the Semantics of Pattern-Matching
    • 5 Efficient Compilation of Pattern-Matching
    • 6 Transforming The Enriched Lambda Calculus
    • 7 List Comprehensions
    • 8 Polymorphic Type-Checking
    • 9 A Type-Checker
  • Part II Graph Reduction
    • 10 Program Representation
    • 11 Selecting the Redex
    • 12 Graph reduction of Lambda Expressions
    • 13 Supercombinators and Lambda-lifting
    • 14 Recursive Supercombinators
    • 15 Fully-Lazy Lambda-Lifting
    • 16 SK Combinators
    • 17 Storage Management and Garbage Collections
  • Part III Advanced Graph Reduction
    • 18 The G-Machine
    • 19 G-Code Definition and Implementation
    • 20 Optimizations to the G-Machine
    • 21 Optimizing Generalized Tail Calls
    • 22 Strictness Analysis

The Design and Construction of Compilers

1982, Hunter

• Table of Contents
  • 1 The compilation process
  • 2 Language definition
  • 3 Lexical analysis
  • 4 Context-free grammars and tope-down syntax analysis
  • 5 Bottom-up syntax analysis
  • 6 Embedding actions in syntax
  • 7 Compiler design
  • 8 Symbol and mode tables
  • 9 Storage allocation
  • 10 Code generation
  • 11 Generation of machine code
  • 12 Error recovery and diagnostics
  • 13 Writing reliable compilers

Writing Interactive Compilers and Interpreters

1979, Brown

• Table of Contents
  • 1 Planning
    • 1.1 Why interactive?
    • 1.2 Planning use of resources
    • 1.3 Documentation
    • 1.4 Designing the source language and the user interface
    • 1.5 Encoding the compiler
  • 2 The Structure of the Compiler
    • 2.1 Filling the gaps
    • 2.2 Description of terminology and environment
    • 2.3 Source and internal languages
    • 2.4 Incremental compiling
    • 2.5 Re-creating the source program
    • 2.6 Levels of internal language
    • 2.7 True compilers
    • 2.8 Error checking
    • 2.9 Error messages
    • 2.10 Names, scope, and data type
    • 2.11 Dictionaries and tables
    • 2.12 Storage management
    • 2.13 The editor
    • 2.14 Input and output
    • 2.15 Break-ins
    • 2.16 Summary of design
  • 3 The Design of an Internal Language
    • 3.1 Reverse polish notation
    • 3.2 Operators
    • 3.3 Encoding reverse polish
    • 3.4 A brief summary
  • 4 The Translator
    • 4.1 Overall translator organization
    • 4.2 Lexical analysis
    • 4.3 Grammars
    • 4.4 Using grammars for parsing
    • 4.5 Checking and resolving data types
    • 4.6 Semantic actions
  • 5 The Run-Time System
    • 5.1 Error detection and diagnosis
    • 5.2 Executing reverse polish
    • 5.3 Allocating and referencing user variables
    • 5.4 Execution of statements
    • 5.5 String temporaries
  • 6 Other Modules
    • 6.1 The pre-run module
    • 6.2 The re-creator module
    • 6.3 The command module
  • 7 Testing and Issuing
    • 7.1 Testing the compiler
    • 7.2 Issuing
  • 8 Some Advanced and Specialized Topics
    • 8.1 Some special copmilers
    • 8.2 Dynamic compiling

Assemblers, Compilers, and Program Translation

1979, Calingaert

• Table of Contents
  • 1 Overview
  • 2 Assembly
  • 3 Program Modules
  • 4 Macro Procesing
  • 5 Program Translation
  • 6 Initial Source-Language Processing
  • 7 Compilation
  • 8 Preparation for Execution

Compiler Construction: An Advanced Course

1974, Bauer, Eickel

• Table of Contents
  • 1 Introduction
  • 2 Analysis
    • Review of formalisms and notation
    • LL(1) grammars and analysers
    • LR grammars and analysers
    • Lexical analysis
    • Transformational grammars
    • Two-level grammars
    • Semantic analysis
  • 3 Synthesis
    • Relationship of languages to machines
    • Run-time storage management
    • Special run-time organization techniques for Algol 68
    • Symbol table access
    • Code generation
    • Assembly and linkage
  • 4 Compiler-Compiler
    • Introduction to compiler-compilers
    • Using the CDL compiler-compiler
  • 5 Engineering a compiler
    • Portable and adaptable compilers
    • Structuring compiler development
    • Programming language design
    • What the compiler should tell the user
    • Optimization
  • 6 Appendix
    • Historical remarks on compiler construction

The Theory of Parsing, Translation, and Compiling

1972, Aho, Ullman

Volume 1 Parsing

• Table of Contents
  • 0 Mathematical Preliminaries
    • Concepts from Set Theory
    • Sets of Strings
    • Concepts from Logic
    • Procedures and Algorithms
    • Concepts from Graph Theory
  • 1 An Introduction to Compiling
    • Programming Languages
    • An Overview of Compiling
    • Other Applications of Parsing and Translating Algorithms
  • 2 Elements of Language Theory
    • Representations for Languages
    • Regular Sets, Their Generators, and Their Recognizers
    • Properties of Regular Sets
    • Context-Free Languages
    • Pushdown Automata
    • Properties of Context-Free Languages
  • 3 Theory of Translation
    • Formalisms for Translations
    • Properties of Syntax-Directed Translations
    • Lexical Analysis
    • Parsing
  • 4 General Parsing Methods
    • Backtrack Parsing
    • Tabular Parsing Methods
  • 5 One-pass No Backtrack Parsing
    • LL(k) Grammars
    • Deterministic Bottom-Up Parsing
    • Precedence Grammars
    • Other classes of Shift-Reduce Parsable Grammars
  • 6 Limited Backtrack Parsing Algorithms
    • Limited Backtrack Top-Down Parsing
    • Limited Backtrack Bottom-Up Parsing

Volume 2 Compiling

• Table of Contents
  • 7 Techniques for Parser Optimization
    • Linear Precedence Functions
    • Optimization of Floyd-Evans Parsers
    • Transformations on Sets of LR(k) Tables
    • Techniques for Constructing LR(k) Parsers
    • Parsing Automata
  • 8 Theory of Deterministic Parsing
    • Theory of LL Languages
    • Classes of Grammars Generating the Deterministic Languages
    • Theory of Simple Precedence Languages
  • 9 Translation and Code Generation
    • The Role of Translation in Compiling
    • Syntax-Directed Translation
    • Genealized Translation Schemes
  • 10 Bookkeeping
    • Symbol Tables
    • Property Grammars
  • 11 Code Optimization
    • Optimization of Straight-Line Code
    • Arithmetic Expressions
    • Programs With Loops
    • Data Flow Analysis

Bootstrapping a simple compiler from nothing

Source

Bootstrapping a simple compiler from nothing
============================================

This document describes how I implemented a tiny compiler for a toy
programming language somewhat reminiscent of C and Forth. The funny
bit is that I implemented the compiler in the language itself without
directly using any previously existing software. So I started by
writing raw machine code in hexadecimal and then, through a series of
bootstrapping steps, gradually made programming easier for myself
while implementing better and better "languages".

The complete source code for all the stages is in a tar archive:
<http://www.rano.org/bcompiler.tar.gz>. This text is the README file
from that archive. So, if you are reading this on-line, you can fetch
the tar archive and continue off-line, if you prefer.

The code only runs on i386-linux, though it would be easy to port it
to another operating system on i386, and probably not at all hard to
port it to a different architecture.


HEX1: the boot loader
---------------------

You could input a short program into the memory of an early computer
by using switches on its front panel. This short program might then
read in a longer program from punched cards. To write a program on
punched cards you did not need an editor program, as you could write
new cards using an electro-mechanical card punch and manually insert
and remove cards from the deck. So, if we were using an early
computer, we could really implement a compiler without using any
existing software. Unfortunately, a modern PC has neither front panel
switches nor a punched card reader, so you need some software running
on the machine just to read in a new program. In fact, you probably
need some rather complex software running on the machine: just take a
look at /usr/src/linux/drivers/block/floppy.c, for example.

Since we are doing this on a PC running Linux, we have to define some
other starting point. Rather than use the raw hardware, we start with
these facilities:

 - an operating system;

 - a simple text editor (or we could use Emacs and pretend it's a
   simple text editor);

 - a shell that lets us run a program with file descriptors connected
   to particular files (this way the programs we write only need to
   read from and write to file descriptors and do not have to know
   about opening files);

 - an initial program to convert hexadecimal to binary so that we can
   compose our first programs in hexadecimal, using the text editor,
   and then "compile" them to binary in order to run them (this
   corresponds roughly to the program that you might enter into an
   early computer using front panel switches).

Our initial program is hex1.he (the source in hexadecimal) or hex1
(the binary). If you want to check that hex1 really is the binary
corresponding to hex1.he, you can do a hex dump of it:

	od -Ax -tx1 hex1

If you use hex1 to process hex1.he the result it hex1 again:

	./hex1 < hex1.he | diff - hex1

So we can think of hex1 as a trivial bootstrapping compiler for a
language called HEX1.

Apart from comments and white space, the syntax of HEX1 is
/([0-9a-f]{2})*/. Comments start with '#' and continue to the end of
the line. The semantics of HEX1 is the semantics of machine code,
which is rather complex. Fortunately we can restrict ourselves to a
tiny subset of the full instruction set.

In hex1.he I have put the corresponding assembler code in comments
next to the machine code. The file starts with two ELF headers: a
52-byte file header and a 32-byte program header. It is not necessary
to understand all the fields in the ELF header. The most interesting
fields are:

* e_entry, which specifies where execution should begin. Here it is
0x08048054, which is directly after the ELF headers (labelled _start).

* p_vaddr and p_paddr, which specify the target address in memory.
Here it is 0x08048000, which is standard for Linux binaries.

* p_filesz and p_memsz, which should be set to the length of the file.
It seems not to matter if you put a larger number here, and I will
make use of that later, though here I have put the correct value.

(For more information about ELF do a web search. SCO and Intel have
some useful on-line documents.)

The code at _start is a loop that reads pairs of hex digits by calling
gethex and outputs bytes by calling putchar. Next comes putchar, which
uses the "write" system call. Then gethex, which calls getchar and
contains a loop for skipping over comments. The ASCII characters
[0-9a-f] are converted correctly to the values 0 to 15; everything
below '0' (48) is treated as a space and ignored; other characters are
misconverted, as there is no error detection. The function getchar
uses the "read" system call, and calls "exit" at the end of the file.


HEX2: one-character labels
--------------------------

Writing machine code in hex is not much fun. The worst part is
calculating the addresses for branch, jump and call instructions. Here
I am using relative addresses, so I have to recalculate the address
every time I change the length of the code between an instruction and
its target. It would be no better if I were using absolute addresses:
then I would have to change all references to locations after the
change.

So the first feature I add for my convenience is a function for
computing relative addresses. Instead of writing

	# function:
		...
		e8 cc ff ff ff		# call function

I will be able to write:

	.F			# function:
		...
		e8 F			# call function

HEX2 automatically fills in the correct 4-byte relative address.

Unfortunately, I still have to use HEX1 to implement the first version
of HEX2, so, to keep the implementation simple, I only allow
one-character labels and backwards references to them. And there is no
error detection for an undefined label.

The syntax of HEX2 is ([0-9a-f]{2}|\.L|L)*, where L is any character
above 32 apart from [0-9a-f].

The first implementation of HEX2 is hex2a.he. If you compare the ELF
headers in hex1.he and hex2a.he you will notice that I have changed
p_flags. This is to make the program writable as well as executable.
Normal programs consist of several sections, in particular a text
section, which contains the program itself, and a data section. The
text section is executable, but not writable, and the data section is
writable, but not executable. In hex1.he I did not need to write any
data to memory, so I only had a text section. In hex2a.he I need to
write data to memory, but I can not be bothered with separate
sections, so I use a single section which is both executable and
writable.

There are only two pieces of data: "pos" is a 32-bit counter to keep
track of our location as we output the binary, and "label" is a
259-byte table to record the values of the labels. Why 259 bytes? This
is because I forgot to multiply by 4. I should have used a table of
256 4-byte values, one for each possible one-character label, and
calculated the address as (table + char * 4). Since I forgot to
multiply by 4, I only need 259 bytes for my table, and I have to avoid
using labels that are close to one another: if I use 'm', then I
cannot use 'j', 'k', 'l', 'n', 'o' or 'p'. It would be easy to fix
this bug immediately, but it is even easier to work around it for now
and fix it a bit later.

We can "compile" hex2a.he using hex1:

	./hex1 < hex2a.he > hex2a && chmod +x hex2a

Since HEX2 is a superset of HEX1, hex2a.he can also compile itself:

	./hex2a < hex2a.he | diff - hex2a

To test the new facility, I made hex2b.he from hex2a.he by replacing
numerical addresses by symbolic ones wherever possible. Compiling
hex2b.he gives the same binary as hex2a.he:

	./hex2a < hex2b.he | diff - hex2a

In hex2c.he I fix the "multiply by 4" bug. It is easier to fix the bug
now that I can use labels and do not have to manually modify relative
addresses. In hex2c.he I also replace some 1-byte relative addresses
by 4-byte relative addresses, so that I can use labels, and I have
inserted blocks of NOPs at the end of file to make the precise value
of e_entry less critical.

We can compile hex2c.he using hex2a/hex2b or using itself:

	./hex2a < hex2c.he > hex2c && chmod +x hex2c
	./hex2c < hex2c.he | diff - hex2c


HEX3: four-character labels and a lot of calls
----------------------------------------------

One-character labels are a bit restrictive, so let us implement
four-character labels. If labels have exactly four characters we can
store them neatly in 32-bit words!

The syntax of HEX3 is /([0-9a-f]{2}|:....|\.....)*/, and now we will
introduce some very basic error detection. The compiler can report
three different kins of error, which is will do using its exit code:

 exit code 1: syntax error
 exit code 2: redefined label
 exit code 3: undefined label

Since it is a single-pass compiler, only backwards references to
labels are permitted.

The first implementation of HEX3 was hex3a.he, written in HEX2:

	./hex2c < hex3a.he > hex3a && chmod +x hex3a

It is not possible to compile hex3a.he with hex3a itself, as HEX3 is
not compatible with HEX2.

I created hex3a.he by making successive small changes to hex2c.he. The
system call brk() is used to get memory for an arbitrarily large
symbol table. Absolute references to data are avoided by putting a
function (.z / get_p) in front of the static data area that returns
the address of the following data.

Having created hex3a.he, I started work on hex3b.he, an implementation
of HEX3 written in HEX3. Initially hex3b.he was just hex3a.he
translated to the new syntax, but I then gradually rewrote it to make
much greater use of labels and functions. In the final version, after
a certain point in the file, everything is done using only these
instruction groups:

 - push a constant onto the stack:  68 XX XX XX XX
 - call a named function:           e8 .LABEL
 - unconditional jump:              e9 .LABEL
 - conditional branch:              58 85 c0 0f 85 .LABEL
 - push an address onto the stack:  68 .LABEL e8 .reab

The last instruction group consists of a push instruction followed by
a call instruction, but the two may not be separated: the function
"reab" converts the relative address on the stack to an absolute
address by adding its return address and subtracting 5.

We can compile hex3b.he using hex3a or itself:

	./hex3a < hex3b.he > hex3b && chmod +x hex3b
	./hex3b < hex3b.he | diff - hex3b


HEX4: any-length labels and implicit calls
------------------------------------------

When implementing hex3b.he we found that it is possible to define all
complex functions in terms of simpler functions by using a tiny subset
of all the possible machine instructions: branch, call, jump and a few
others.

In HEX4 we use an even smaller set of instructions and generate those
instructions implicitly.

In HEX4 there are four types of token:

 - in-line code or data ('58, '59)
 - define label (:data, :loop, :func)
 - instruction: push constant (10, 42)
 - instruction: push label address (&func;, &loop;)
 - instruction: call label address (+, -, jump, branch, func)

Tokens must be separated by white space and the type of token is
recognised from the first character. Labels can have any length - but
we implement them with a simple hash function, so there is a risk of
spurious redefined label errors.

The jump and branch instruction groups from HEX3 are implemented by
functions. A "push label address" instruction must always be followed
immediately by a call to one of the functions that can understand a
relative address: address, branch, jump. The "address" function
(formally "reab") converts the relative address to an absolute
address, which can be stored and used later.

The predefined functions are:

Stack manipulation: drop dup rot pick swap
Arithmetic: + - * / % << >> log
Comparisons: < <= == != >= >
Bitwise logic: & | ^ ~
Memory access: @ = c@ c=
Flow of control, using immediate relative address: branch call
Flow of control, using stored absolute address: call
Address conversion: address
Array support: [] []& []= c[] c[]& c[]=
Access of arguments and variables: arg arg& arg= var var& var=
Function support: enter vars xreturnx xreturn0 xreturn1
Dynamic memory: wsize sbrk / malloc free realloc
System calls: exit in out

- All operations take arguments and return results to the stack.

- Comparisons return 0 or 1.

- All data are words, except for c@, c=, c[], c[]&, c[]=, which
operate on bytes.

- Any user-defined function must start with "enter"; "vars" can be
used straight after "enter" to reserve space for N local variables.

- To return from a function, use one of the "return" functions. "X Y
xreturnx" means return Y values from a function that took X arguments.
The most common cases are Y=0 and Y=1, so "X xreturn0" and "X
xreturn1" are provided.

- Like in C, addresses are byte addresses, so we have to multiply by
wsize when allocating memory with sbrk or malloc.

- "x y []" is equivalent to "x y wsize * + @"

- As always, no forward references to labels are allowed.

As with HEX3 there are two implementations of HEX4. The first one,
hex4a.he, is written in HEX3. The second one, hex4b.he, is written in
HEX4.

	./hex3b < hex4a.he > hex4a && chmod +x hex4a
	./hex4a < hex4b.he > hex4b && chmod +x hex4b
	./hex4b < hex4b.he | diff - hex4b


HEX5: structured programming, at last
-------------------------------------

HEX5 is more like a real structured programming language. There are no
longer any labels; instead there are loops and if...(else)...fi
structures. The syntax of HEX5 can no longer be described with a
regular expression; instead we need a context-free grammar:

	program = (hexitem | global | procedure)*
	hexitem = hexbyte |  "_def" symbol
	hexbyte = /'[0-9a-f][0-9a-f]/
	global = "var" symbol | "string" symbol string_literal
	string_literal = /"([^"]|\\.)*"/
	procedure = "def" args name "{" vars body "}"
	args = symbol*
	name = symbol
	vars = "var" symbol
	body = (number | word | loop | jump | if)*
	number = /[0-9]+/
	word = symbol
	loop = "{" body "}"
	jump = "break" | "continue" | "until" | "while"
	if = "if" body "fi" | "if" body "else" body "fi"
	symbol = /.+/ except ...

Lexical rules:

	comment = /#[^\n]*\n?/
	space = /\s/
	string_literal = /"([^"]|\\.)*"/
	token = /\S+/

The first implementation of HEX5, written in HEX4, is hex5a.he. This
is only a very partial implementation, as it would be quite tedious to
implement all of HEX5 in HEX4. In particular, there are not yet any
named variables or arguments; access to a function's arguments and
local variables is done using the functions from HEX4. Global
variables are implemented with a cunning hack:

	./hex4b < hex5a.he > hex5a && chmod +x hex5a

Next came hex5b.he, which can compile itself, as it is written in a
subset of HEX5. In hex5b.he I implemented named arguments and
variables:

	./hex5a < hex5b.he > hex5b && chmod +x hex5b
	./hex5b < hex5b.he | diff - hex5b

Then I wanted to start using those features for implementing further
features, so I switched to developing hex5c.he, in which I implemented
string constants, "while", "until", "return0" and "return1":

	./hex5b < hex5c.he > hex5c && chmod +x hex5c


BCC: a real language
--------------------

All that is needed to turn HEX5 into a tiny structured programming
language is to separate off the first part of the source, where there
is in-line machine code and the "predefined" and library functions are
implemented, into a separate header file. At this point I removed
references to "hex" and called the two files "header.bc" and "bcc.bc".
These two files are concatenated for compilation:

	cat header.bc bcc.bc | ./hex5c > bcc && chmod +x bcc

Now bcc can compile itself, of course:

	cat header.bc bcc.bc | ./bcc > bcc2 && chmod +x bcc2
	mv bcc2 bcc
	cat header.bc bcc.bc | ./bcc | diff - bcc

Note that the bcc produced by hex5 might not be identical to the bcc
produced by bcc itself, as I might make some minor improvements to the
code generated by bcc. But the main improvements to be introduced in
bcc are:

 - proper error messages to stderr instead of just exit codes
 - report undefined symbols
 - a dynamic buffer for tokens so there is no limit to their length


What next?
----------

Here are some things that one might want to do with BCC for one's
education and entertainment:

 - port it to a different operating system or architecture
   (you could compile to Java byte code, for example)

 - think of a neater way of handling return values from functions

 - implement a compile-time check for stack underflow

 - include a non-bogus implementation of malloc, realloc, free

 - use an RB-tree for the symbol table so that the compiler does not
   take time quadratic in the number of symbols

 - think up a way of using BCC to bootstrap GCC ...


Edmund GRIMLEY EVANS <edmundo@xxxx.xxx>, March 2001
Revised: March 2002

Dynamic Languages Are Static Languages

2011

• Source

A dynamic language is a straightjacketed static language that affords less rather than more expressiveness.

So-called dynamic languages (“so-called” because I’m going to argue that they don’t exist as a separate class of languages) are popular.

Part of the appeal of dynamic languages appears to be that they have acquired an aura of subversion. Dynamic languages fight against the tyranny of static languages, hooray for us! We’re the heroic blackguards defending freedom from the tyranny of typing! We’re real programmers, we don’t need no stinking type system!

Now I’m as susceptible to the seductions of subversion as the next guy (witness this very post), so I can appreciate wanting to strike one for the little guy, overturning the evil establishment. But I’ve got news for you: when it comes to “dynamic typing”, it’s a futile enterprise. Not because the establishment is so powerful. Not because evil always wins. But because the distinction makes no sense. Dynamic typing is but a special case of static typing, one that limits, rather than liberates, one that shuts down opportunities, rather than opening up new vistas. Need I say it? Something can hardly be opposed to that of which it is but a trivial special case. So, give it up, and get with the program! There are ill-defined languages, and there are well-defined languages. Well-defined languages are statically typed, and languages with rich static type systems subsume dynamic languages as a corner case of narrow, but significant, interest.

Wittgenstein said that all philosophical problems are problems of grammar. And so it is here as well. The root of the problem lies in the confusion between a type and a class. We all recognize that it is often very useful to have multiple classes of values of the same type. The prototypical example is provided by the complex numbers. There is one type of complex numbers that represent points in two-dimensional space. In school we encounter two classes of complex numbers, the rectangular and the polar. That is, there are two ways to present a complex number using two different systems of coordinates. They are, of course, interchangeable, because they represent values of the same type. But the form of presentation differs, and some forms are more convenient than others (rectangular for addition, polar for multiplication, for example). We could, of course, choose a “coin of the realm”, and represent all complex numbers in one way, and consider coordinates as just a matter of how a number is given. But it can also be convenient to consider that the type of complex numbers consists of two classes, each of which consists of two real numbers, but interpreted differently according to the coordinate system we are using.

Crucially, the distinction between the two classes of complex number is dynamic in that a given computation may result in a number of either class, according to convenience or convention. A program may test whether a complex number is in polar or rectangular form, and we can form data structures such as sets of complex numbers in which individual elements can be of either form. But this does not conflict with the basic fact that there is but one static type of complex numbers! In type theoretic terms what I am saying is that the type complex is defined to be the sum of two copies of the product of the reals with itself. One copy represents the class of rectangular representations, the other represents the class of polar representations. Being a sum type, we can “dispatch” (that is, case analyze) on the class of the value of the type complex, and decide what to do at run-time. This is no big deal. In fact, it’s quite simple and natural in languages such as ML or Haskell that support sum types. (Languages that don’t are hobbled, and this is part of the confusion.)

What does this have to do with the concept of a dynamic language? The characteristics of a dynamic language are the same, values are classified by into a variety of forms that can be distinguished at run-time. A collection of values can be of a variety of classes, and we can sort out at run-time which is which and how to handle each form of value. Since every value in a dynamic language is classified in this manner, what we are doing is agglomerating all of the values of the language into a single, gigantic (perhaps even extensible) type. To borrow an apt description from Dana Scott, the so-called untyped (that is “dynamically typed”) languages are, in fact, unityped. Rather than have a variety of types from which to choose, there is but one!

And this is precisely what is wrong with dynamically typed languages: rather than affording the freedom to ignore types, they instead impose the bondage of restricting attention to a single type! Every single value has to be a value of that type, you have no choice! Even if in a particular situation we are absolutely certain that a particular value is, say, an integer, we have no choice but to regard it as a value of the “one true type” that is classified, not typed, as an integer. Conceptually, this is just rubbish, but it has serious, tangible penalties. For one, you are depriving yourself of the ability to state and enforce the invariant that the value at a particular program point must be an integer. For another, you are imposing a serious bit of run-time overhead to represent the class itself (a tag of some sort) and to check and remove and apply the class tag on the value each time it is used. (See PFPL for full details of what is involved.)

Now I am fully aware that “the compiler can optimize this away”, at least in some cases, but to achieve this requires one of two things (apart from unreachable levels of ingenuity that can easily, and more profitably, be expressed by the programmer in the first place). Either you give up on modular development, and rely on whole program analysis (including all libraries, shared code, the works), or you introduce a static type system precisely for the purpose of recording inter-modular dependencies. The whole-program approach does not scale, and flies in the face of the very advantage that dynamic languages supposedly have, namely dynamic evolution and development of components. The static type system approach works beautifully, and makes my point nicely.

I am also fully aware that many statically typed languages, particularly the ones widely in commercial use, do not have a sufficiently expressive type system to make it feasible to work dynamically (that is, with multiple classes of values) within a statically typed framework. This is an argument against bad languages, not an argument against type systems. The goal of (static, there is no other kind) type systems is precisely to provide the expressive power to capture all computational phenonema, including dynamic dispatch and dynamically extensible classification, within the rich framework of a static type discipline. More “researchy” languages such as ML or Haskell, have no trouble handling dynamic modes of programming.

Why should you care? Because, I argue, that a fully expressive language is one that supports the delicate interplay between static and dynamic techniques. Languages that force only one perspective on you, namely the dynamic languages, hobble you; languages that admit both modes of reasoning enable you and liberate you from the tyranny of a single type.

LLVM

• Online Resources
  • Documentation, Tutorials
    • MLIR
  • Youtube
  • Applications
    • Clang Analyzer
    • Polly
  • Bindings
    • Rust
• Books
  • LLVM Essentials
  • Learn LLVM 12
  • Getting Started with LLVM Core Libraries
  • LLVM Cookbook
  • LLVM Techniques, Tips, and Best Practices Clang and Middle-End Libraries

Online Resources

Documentation, Tutorials

• LLVM Docs
• LLVM Discourse
• Awesome LLVM
• 2011/05/26 ⚠️ The Architecture of Open Source Applications: LLVM
• 2011/10/14 Stack Overflow: Is it possible to use LLVM-assembly directly?
• 2012/02/05 Stack Overflow: How to make clang compile to llvm IR
• 2013/07/24 IR is better than assembly
• 2015/09/08 ⚠️ XRay the LLVM/Clang source code
• 2016/02/15 How To Write An LLVM Register Allocator
• 2016/10/25 ⚠️ Mapping High Level Constructs to LLVM IR
• 2016/11/10 LLVM Optimizations
• 2019/10/01 Combining GNAT with LLVM
• 2020/01/19 Gandiva, using LLVM and Arrow to JIT and evaluate Pandas expressions
• 2020/05/10 Make LLVM fast again
• 2020/09/28 Zig's New Relationship with LLVM
• 2020/12/24 ⚠️ A Complete Guide to LLVM for Programming Language Creators
• 2021/04/13 Reducing code size with LLVM Machine Outliner on 32-bit Arm targets
• 2021/05/20 Building LLVM in 90 seconds using Amazon Lambda L.rs
• 2021/06/02 ⚠️ Design issues in LLVM IR
• 2021/06/11 Can memcpy be implemented in LLVM IR? L.rs
• 2021/07/16 ⚠️ A Journey to understand LLVM IR
• 2021/08/09 Intel C/C++ compilers complete adoption of LLVM
• 2021/08/13 Exploring Clang/LLVM optimization on programming horror
• 2021/09/06 ⚠️ Learning Almost Nothing About LLVM
• 2021/11/04 ⚠️ How to Learn Compilers: LLVM Edition
• 2021/18/04 [llvm-dev] Inline function not eventually inlined is removed
• 2022/09/21 What's new for RISC-V in LLVM 15
• 2022/11/17 Compiling Containers - Dockerfiles, LLVM, and BuildKit
• 2023/01/09 ⚠️ Mapping Python to LLVM
• LLVM Blog
• John Regehr
  • 2017/01/07 ⚠️ A Tourist’s Guide to the LLVM Source Code
  • 2017/04/15 Taming Undefined Behavior in LLVM
• Eli Bendersky
  • 2017/03/20 Adventures in JIT compilation: Part 1 - an interpreter
  • 2017/03/22 Adventures in JIT compilation: Part 2 - an x64 JIT
  • 2017/05/01 Adventures in JIT compilation: Part 3 - LLVM
• William Woodruff
  • 2020/09/19 LLVM's getelementptr, by example
  • 2020/10/23 ⚠️ Understanding static single assignment forms
  • 2021/07/19 ⚠️ LLVM internals, part 1: the bitcode format
  • 2021/08/10 ⚠️ LLVM internals, part 2: parsing the bitstream
  • 2021/09/14 ⚠️ LLVM internals, part 3: from bitcode to IR
  • 2021/11/29 ⚠️ LLVM internals, part 4: attributes and attribute groups
  • 2022/04/30 ⚠️ LLVM internals, part 5: a very brief update
• Harlan Haskins
  • 2017/01/08 Building a Compiler in Swift with LLVM, Part 1: Introduction and the Lexer
  • 2017/01/09 Building a Compiler in Swift with LLVM, Part 2: AST and the Parser
  • 2017/01/11 Building a Compiler in Swift with LLVM, Part 3: Code Generation to LLVM IR
• Phil Eaton
  • Github - eatonphil/ulisp: A compiler for a lisp-like language targeting LLVM IR, x86 assembly
  • 2018/11/20 Writing a lisp compiler from scratch in JavaScript: 1. lisp to assembly
  • 2019/01/20 Writing a lisp compiler from scratch in JavaScript: 2. user-defined functions and variables
  • 2019/03/10 Writing a lisp compiler from scratch in JavaScript: 3. LLVM
  • 2019/05/04 Writing a lisp compiler from scratch in JavaScript: 4. LLVM conditionals and compiling fibonacci
  • 2019/06/22 Writing a lisp compiler from scratch in JavaScript: 5. LLVM system calls
  • 2019/12/08 Writing a lisp compiler from scratch in JavaScript: 6. an x86 upgrade

MLIR

• Lei Zhang
  • 2021/09/19 CodeGen Performant Convolution Kernels for Mobile GPUs
  • 2022/01/08 Compilers and IRs: LLVM IR, SPIR-V, and MLIR
  • 2022/02/20 MLIR CodeGen Dialects for Machine Learning Compilers
  • 2022/07/21 MLIR Vector Dialect and Patterns
  • 2022/08/31 MLIR Linalg Dialect and Patterns
• LLVM/MLIR Toy Language Tutorial
• How to build a compiler with LLVM and MLIR

Youtube

• LLVM in 100 Seconds
• LVVM Project Youtube Channel
  • 2017 LLVM Developers' Meeting
  • 2017 LLVM Lightning Talks
  • 2018 EuroLLVM Developers' Meeting
  • 2018 LLVM Developers' Meeting
  • 2019 EuroLLVM Developers' Meeting
  • 2019 LLVM Developers' Meeting
    • 2019/11/18 2019 LLVM Developers’ Meeting: “Writing an LLVM Pass: 101”
  • 2019 LLVM Lightning Talks
  • 2022 LLVM Developer's Meeting
• Tim Morgan
  • 2021/10/25 Compiling with LLVM | Emit LLVM IR | C++ | Compiler Hacking
  • 2021/11/08 Compiling puts with LLVM | C++ | Compiler Hacking
  • 2021/11/09 Adding Variables in LLVM | C++ | Compiler Hacking
  • 2021/11/11 Adding Operators in LLVM | C++ | Compiler Hacking
• Compilers Lab
• 2019/04/28 2019 EuroLLVM Developers’ Meeting: “LLVM IR Tutorial - Phis, GEPs, and other things”
• 2021/08/16 Modular, Compositional, and Executable Formal Semantics for LLVM IR
• 2021/12/13 Nick Baron - Reading LLVM IR
• 2021/12/13 Making LLVM IR
• 2021/12/02 Tutorial: LLVM for Security Practitioners
• 2022/06/18 Rust versus DWARF versus LLVM

Applications

• GitHub - ark-lang/ark: A compiled systems programming language written in Go using the LLVM framework
• Github - banach-space/llvm-tutor: A collection of out-of-tree LLVM passes for teaching and learning
• GitHub - brain-labs/brain: An esoteric programming language compiler on top of LLVM based on Brainfuck
• Github - dibyendumajumdar/dmr_c: dmr_C is a C parser and JIT compiler with LLVM, Eclipse OMR and NanoJIT backends
• GitHub - froggey/Iota: LLVM to Common Lisp transpiler.
• Github - G3orge26/llvm-memlog-pass: A complete guide to writing an LLVM Pass
• Github - google/llvm-propeller: PROPELLER: Profile Guided Optimizing Large Scale LLVM-based Relinker
• GitHub - igor84/summus: Simple compiler frontend using LLVM as backend
• Designing ParaSail, a new programming language: Compiling ParaSail to LLVM, first in a series...
• ErLLVM

Clang Analyzer

• clang-analyzer.llvm.org/
• How to write a checker in 24 hours

Polly

• Polly: LLVM Framework for High-Level Loop and Data-Locality Optimizations

Bindings

Rust

Books

LLVM Essentials

• Table of Contents
  • 1 Playing with LLVM
    • Modular design and collection of libraries
    • Getting familiar with LLVM IR
    • LLVM tools and using them in the command line
  • 2 Building LLVM IR
    • Creating an LLVM module
    • Emitting a function in a module
    • Adding a block to a function
    • Emitting a global variable
    • Emitting a return statement
    • Emitting function arguments
    • Emitting a simple arithmetic statement in a basic block
    • Emitting if-else condition IR
    • Emitting LLVM IR for loop
  • 3 Advanced LLVM IR
    • Memory access violations
    • Getting the address of an element
    • Reading from the memory
    • Writing into a memory location
    • Inserting a scalar into a vector
    • Extracting a scalar from a vector
  • 4 Basic IR Tranformations
    • Opt tool
    • Pass and Pass Manager
    • Using other pass info in the current pass
    • Instruction simplification example
    • Instruction combining
  • 5 Advanced IR Blokc Transformations
    • Loop processing
    • Scalar evolution
    • LLVM intrinsics
    • Vectorization
  • 6 IR to Selection DAG Phase
    • Converting IR to SelectionDAG
    • Legalizing SelectionDAG
    • Optimizing SelectionDAG
    • Instruction selection
    • Scheduling and emitting machine instructions
    • Register allocation
    • Code emission
  • 7 Generating Code for Target Architecture
    • Sample backend
    • Implementing frame lowering
    • Lowering instructions
    • Printing an instruction

Learn LLVM 12

• Table of Contents
  • Section 1 The Basic of Compiler Construction with LLVM
    • 1 Installing LLVM
    • 2 Touring the LLVM Source Code
    • 3 The Structure of the Compiler
  • Section 2 From Source Code to Machine Code Construction
    • 4 Turning the Source File into an Abstract Syntax Tree
    • 5 Basic of IR Code Generation
    • 6 IR Generation for High-level Language Constructs
    • 7 Advanced IR Generation
    • 8 Optimizing IR
  • Section 3 Taking LLVM to the Next Level
    • 9 Instruction Selection
    • 10 JIT Compilation
    • 11 Debugging with LLVM Tools
    • 12 Create your own backend

Getting Started with LLVM Core Libraries

• Table of Contents
  • 1 Build and install LLVM
  • 2 External Projectos
  • 3 Tools and Design
  • 4 The Frontend
  • 5 The LLVM Intermediate Representation
  • 6 The Backend
  • 7 The Just-In-Time Compiler
  • 8 Cross-platform Compilation
  • 9 The Clang Static Analyzer
  • 10 Clang Tools with LibTooling

LLVM Cookbook

• Table of Contents
  • 1 LLVM Design and Use
    • Introduction
    • Understanding modular design
    • Cross-compiling Clang/LLVM
    • Converting a C source code to LLVM assembly
    • Converting IR to LLVM bitcode
    • Converting LLVM bitcode back to target machine assembly
    • Transforming LLVM IR
    • Linking LLVM bitcode
    • Executing LLVM bitcode
    • Using the C frontend Clang
    • Using the GO frontend
    • Using DragonEgg
  • 2 Steps in Writing a Frontend
    • Introduction
    • Defining a TOY Language
    • Implementing a lexer
    • Defining Abstract Syntax Trees
    • Implementing a parser
    • Parsing simple expressions
    • Parsing binary expressions
    • Invoking a driver for parsing
    • Running lexer and parser on our TOY language
    • Defining IR code generation methods for each AST class
    • Generating IR code for expressions
    • Generating IR code for functions
    • Adding IR optimizations support
  • 3 Extending the Frontend and Adding JIT Support
    • Introduction
    • Handling decision making paradigms - if/then/else constructs
    • Generating code for loops
    • Handling user-defined operators - binary operators
    • Handling user-defined operators - unary operators
    • Adding JIT support
  • 4 Preparing Optimizations
    • Introduction
    • Various levels of optimization
    • Writing your own LLVM pass
    • Running your own pass with the opt tool
    • Using another pass in a new pass
    • Registering a pass with pass manager
    • Writing an analysis pass
    • Writing an alias analysis pass
    • Using other analysis passes
  • 5 Implementing Optimizations
    • Introduction
    • Writing a dead code elimination pass
    • Writing an inlining transformation pass
    • Writing a pass for memory optimization
    • Combining LLVM IR
    • Transforming and optimizing loops
    • Reassociating expressions
    • Vectorizing IR
    • Other optimization passes
  • 6 Target-independent Code Generator
    • Introduction
    • The life of an LLVM IR instruction
    • Machine DAG
    • Visualizing LLVM IR CFG using GraphViz
    • Describing targets using TableGen
    • Defining an instruction set
    • Adding a machine code descriptor
    • Implementing the MachineInstrBuilder class
    • Implementing the MachineBasicBlock class
    • Implementing the MachineFunction class
    • Writing an instruction selector
    • Legalizing SelectionDAG
    • Optimizing SelectionDAG
    • Selecting instruction from the DAG
    • Scheduling instructions in SelectionDAG
  • 7 Optimizing the Machine Code
    • Introduction
    • Eliminating common subexpression from machine code
    • Analyzing live internals
    • Allocating registers
    • Inserting the prologue-epilogue code
    • Code emission
    • Tail call optimization
    • Sibling call optimization
  • 8 Writing an LLVM Backend
    • Introduction
    • Defining registers and registers sets
    • Defining the calling convention
    • Defining the instruction set
    • Implementing frame lowering
    • Printing an instruction
    • Selecting an instruction
    • Adding an instruction encodeing
    • Supporting a subtarget
    • Lowering to multiple instructions
    • Registering a target
  • 9 Using LLVM for Various Useful Projects
    • Introduction
    • Exception handling in LLVM
    • Using sanitizers
    • Writing the garbage collector with LLVM
    • Converting LLVM IR to JavaScript
    • Using the Clang Static Analyzer
    • Using bugpoint
    • Using LLDB
    • Using LLVM utility passes

LLVM Techniques, Tips, and Best Practices Clang and Middle-End Libraries

• Table of Contents
  • Section 1 Build System and LLVM-specific Tooling
    • 1 Saving resources when building LLVM
    • 2 Exploring LLVM's Build System Features
    • 3 Testing with LLVM LIT
    • 4 TableGen Development
  • Section 2 Frontend Development
    • 5 Exploring Clang's Architecture
    • 6 Extending the Preprocessor
    • 7 Handling AST
    • 8 Working with Compiler Flags and Toolchains
  • Section 3 Middle-End Management
    • 9 Working with PassManager and AnalysisManager
    • 10 Processing LLVM IR
    • 11 Gearing up with Support Utilities
    • 12 Learning LLVM IR Instrumentation

Static Analysis

Some of the implementation techniques of formal static analysis include:

• Model checking considers systems that have finite state or may be reduced to finite state by abstraction;

• Data-flow analysis is a lattice-based technique for gathering information about the possible set of values;

• Abstract interpretation models the effect that every statement has on the state of an abstract machine (i.e., it 'executes' the software based on the mathematical properties of each statement and declaration). This abstract machine over-approximates the behaviours of the system: the abstract system is thus made simpler to analyze, at the expense of incompleteness (not every property true of the original system is true of the abstract system). If properly done, though, abstract interpretation is sound (every property true of the abstract system can be mapped to a true property of the original system). The Frama-c value analysis plugin and Polyspace heavily rely on abstract interpretation.

• Use of assertions in program code as first suggested by Hoare logic. There is tool support for some programming languages (e.g., the SPARK programming language (a subset of Ada) and the Java Modeling Language — JML — using ESC/Java and ESC/Java2, Frama-c WP (weakest precondition) plugin for the C language extended with ACSL (ANSI/ISO C Specification Language)).

Why inheritance never made any sense

• Source

There are three different types of inheritance going on.

• Ontological inheritance is about specialisation: this thing is a specific variety of that thing (a football is a sphere and it has this radius)
• Abstract data type inheritance is about substitution: this thing behaves in all the ways that thing does and has this behaviour (this is the Liskov substitution principle)
• Implementation inheritance is about code sharing: this thing takes some of the properties of that thing and overrides or augments them in this way. The inheritance in my post On Inheritance is this type and only this type of inheritance.

These are three different, and frequently irreconcilable, relationships. Requiring any, or even all, of them, presents no difficulty. However, requiring one mechanism support any two or more of them is asking for trouble.

A common counterexample to OO inheritance is the relationship between a square and a rectangle. Geometrically, a square is a specialisation of a rectangle: every square is a rectangle, not every rectangle is a square. For all s in Squares, s is a Rectangle and width of s is equal to height of s. As a type, this relationship is reversed: you can use a rectangle everywhere you can use a square (by having a rectangle with the same width and height), but you cannot use a square everywhere you can use a rectangle (for example, you can’t give it a different width and height).

Notice that this is incompatibility between the inheritance directions of the geometric properties and the abstract data type properties of squares and rectangles; two dimensions which are completely unrelated to each other and indeed to any form of software implementation. We have so far said nothing about implementation inheritance, so haven’t even considered writing software.

Smalltalk and many later languages use single inheritance for implementation inheritance, because multiple inheritance is incompatible with the goal of implementation inheritance due to the diamond problem (traits provide a reliable way for the incompatibility to manifest, and leave resolution as an exercise to the reader). On the other hand, single inheritance is incompatible with ontological inheritance, as a square is both a rectangle and an equilateral polygon.

The Smalltalk blue book describes inheritance solely in terms of implementation inheritance:

A subclass specifies that its instances will be the same as instances of another class, called its superclass, except for the differences that are explicitly stated.

Notice what is missing: no mention that a subclass instance must be able to replace a superclass instance everywhere in a program; no mention that a subclass instance must satisfy all conceptual tests for an instance of its superclass.

Inheritance was never a problem: trying to use the same tree for three different concepts was the problem.

“Favour composition over inheritance” is basically giving up on implementation inheritance. We can’t work out how to make it work, so we’ll avoid it: get implementation sharing by delegation instead of by subclassing.

Eiffel, and particular disciplined approaches to using languages like Java, tighten up the “inheritance is subtyping” relationship by relaxing the “inheritance is re-use” relationship (if the same method appears twice in unrelated parts of the tree, you have to live with it, in order to retain the property that every subclass is a subtype of its parent). This is fine, as long as you don’t try to also model the problem domain using the inheritance tree, but much of the OO literature recommends that you do by talking about domain-driven design.

Traits approaches tighten up the “inheritance is specialisation” relationship by relaxing the “inheritance is re-use” relationship (if two super categories both provide the same property of an instance of a category, neither is provided and you have to write it yourself). This is fine, as long as you don’t try to also treat subclasses as covariant subtypes of their superclasses, but much of the OO literature recommends that you do by talking about Liskov Substitution Principle and how a type in a method signature means that type or any subclass.

What the literature should do, I believe, is say “here are the three types of inheritance, focus on any one of them at a time”. I also believe that the languages should support that (obviously Smalltalk, Ruby and friends do support that by not having any type constraints).

If I’m using inheritance as a code sharing tool, it should not be assumed that my subclasses are also subtypes.
If I am using subtypes to tighten up interface contracts, I should be not only allowed to mark a class anywhere in the tree as a subtype of another class anywhere in the tree, but required to do so: once again, it should not be assumed that my subclasses are also subtypes.
If I need to indicate conceptual specialisation via classes, this should also not be assumed to follow the inheritance tree. I should be not only allowed to mark a class anywhere in the tree as a subset of another class, but required to do so: once again, it should not be assumed that my subclasses are also specialisations.

Your domain model is not your object model. Your domain model is not your abstract data type model. Your object model is not your abstract data type model.

Now inheritance is easy again.

Incremental Compilation

• Tesina Iñaki

Background material

• 2016/12 Youtube: “2016 LLVM Developers’ Meeting: A New Architecture for Building Software”, Daniel Dunbar
• 2017/01 Youtube: "Anders Hejlsberg on Modern Compiler Construction", Anders Hejlsberg
• 2018/09 “Build systems a la carte”, Mokhov, Andrey and Mitchell, Neil and Peyton Jones, Simon
• 2020/06 "Query-based compiler architectures", Olle Fredriksson
• 2020/12 Youtube: "A journey through incremental computation", Raph Levien
• 2021/04 "An opinionated map of incremental and streaming systems", Jamie Brandon
• 2021/04 Query Engines: Push vs. Pull HN

Salsa

• Youtube: How Salsa Works (2019.01)
• Youtube: Salsa In More Depth (2019.01)
• Youtube: 2022-01-28 Salsa Architecture Walkthrough
  • Notes
  • Related PR
  • Flowgraph
• Youtube: 2022-02-18: Salsa cycle-handling walkthrough
  • Notes
• 2019/06 "Responsive compilers - PLISS 2019", Nicholas Matsakis
• 2020/07 Youtube: JuliaCon 2020 | Salsa.jl: A framework for on-demand, incremental computation | Nathan Daly

Rust Analyzer

• 2020/01 Youtube: Are we actually IDE yet? A look on the Rust IDE Story - Igor Matuszewski
• 2019/01 Youtube: Rust analyzer guide
• 2019/02 Youtube: rust analyzer syntax trees
• 2019/03 Youtube: RLS 2.0, Salsa, and Name Resolution
• 2019/03 Youtube: rust-analyzer type-checker overview by flodiebold
• Youtube: Playlist: Explaining rust-analyzer
• 2019/12 "Rust Analyzer in 2018 and 2019", Aleksey Kladov
• 2020/07 "Three Architectures for a Responsive IDE", Aleksey Kladov

Rustc incremental compilation

• 2016/09 "Rust Blog: Incremental Compilation", Michael Woerister
• 2021/03 Projects for incremental compilation in rustc
• Incremental Compilation Working Group: Ongoing Projects

Distributed Systems

⚠️ WIP ⚠️

• Online Resources
• Courses
  • UNS Sistemas Distribuidos
    • Programa Sintetico
    • Programa Analitico

Online Resources

Courses

UNS Sistemas Distribuidos

Programa Sintetico

1. Introducción a los Sistemas Distribuidos.
2. Comunicación en Sistemas Distribuidos.
3. Sincronización en Sistemas Distribuidos.
4. Planificación de Procesos en Sistemas Distribuidos.
5. Consistencia, Replicación y Memoria Compartida Distribuida.
6. Sistemas de Archivos en Sistemas Distribuidos.
7. Transacciones Distribuidas.
8. Sistema de Nombres.
9. Tolerancia a las Fallas
10. Seguridad en Sistemas Distribuidos.
11. Sistemas Distribuidos Basados en Documentos

Programa Analitico

• 1.0 - Introducción a los Sistemas Distribuidos.
  • 1.1 Computación paralela y distribuida.
  • 1.2 Desventajas y limitaciones.
  • 1.3 Requerimientos de Hardware y Software.
• 2.0 - Comunicación en Sistemas Distribuidos.
  • 2.1 Pasaje de mensajes
  • 2.2 Modelo Cliente-Servidor
  • 2.3 Llamadas a Procedimiento Remoto
  • 2.4 Grupos de Comunicación
• 3.0 - Sincronización en Sistemas Distribuidos.
  • 3.1 Sincronización de Reloj
  • 3.2 Estado Global
  • 3.3 Exclusión Mutua
  • 3.4 Algoritmos de Elección
  • 3.5 Interbloqueos
• 4.0 - Planificación de Procesos en Sistemas Distribuidos.
  • 4.1 Estrategias de Distribución de Carga.
  • 4.2 Migración de Procesos y Movilidad
• 5.0 - Consistencia, Replicación y Memoria Compartida Distribuida.
  • 5.1 Modelos de Consistencia centrados en los datos
  • 5.2 Modelos de Consistencia centrados en el cliente
  • 5.3 Protocolos de distribución
  • 5.4 Protocolos de consistencia
  • 5.5 Memoria Compartida Distribuida
• 6.0 - Sistemas de Archivos Distribuidos
  • 6.1 Propósito de uso
  • 6.2 Servicios
  • 6.3 Características deseables de los SAD
  • 6.4 Modelos de archivos y sus accesos
  • 6.5 Semánticas
  • 6.6 Esquemas de caché
  • 6.7 Tolerancia a las fallas
• 7.0 - Transacciones Distribuidas
  • 7.1 Modelo Transaccional
  • 7.2 Protocolos de commit
• 8.0 - Sistema de Nombres
  • 8.1 Nombres, Entidades
  • 8.2 Sistema de nombres y localización de objetos
  • 8.3 Remoción de Entidades no Referenciadas
• 9.0 - Tolerancia a las Fallas
  • 9.1 Conceptos básicos
  • 9.2 Enmascaramiento
  • 9.3 Ordenamiento de mensajes
  • 9.4 Checkpointing
• 10.0 - Seguridad en Sistemas Distribuidos
  • 10.1 Introducción
  • 10.2 Ataques
  • 10.3 Criptografía
  • 10.4 Autenticación
  • 10.5 Código móvil
• 11.0 - Sistemas Distribuidos Basados en Documentos
  • 11.1 Caso: WWW

Books

• Designing Data Intensive Applications
• Guide To Reliable Distributed Systems
• Protocol Design
• Introduction to Reliable and Secure Distributed Programming (Carlos Varela, Cachin)
• Distributed Systems Principles and Paradigms (Tanenbaum)
• Distributed Systems: Concepts and Design (Colouris)
• Distributed Operating Systems (Tanenbaum)
• Distributed Operating Systems: Theory and Practice (lamport)
• Distributed Algorithms (Lynch)
• Distributed Algorithms for Message-Passing Systems (raynal)
• Distributed Systems An Algorithmic Approach (Ghosh)
• Distributed Systems An Intuitive Approach (Wan Fokkink)
• Notes on Theory of Distributed Systems
• Scaling Reliably: Improving the Scalability of the Erlang Distributed Actor Platform

Designing Data Intensive Applications

• I foundations of data systems
  • 1 reliable, scalable, and maintainable applications
    • 1.1 thinking about data systems
    • 1.2 reliability
    • 1.3 scalability
    • 1.4 maintainability
  • 2 data models and query languages
    • 2.1 relational model vs document model
    • 2.2 query languages for data
    • 2.3 graph-like data models
  • 3 storage and retrieval
    • 3.1 data structures that power your database
    • 3.2 transaction processing or analytics?
    • 3.3 column-oriented storage
  • 4 encoding and evolution
    • 4.1 formats for encoding data
    • 4.2 modes of dataflow
• II distributed data
  • 5 replication
    • 5.1 leaders and followers
    • 5.2 problems with replication lag
    • 5.3 multi-leader replication
    • 5.4 leaderless replication
  • 6 partitioning
    • 6.1 partitioning and replication
    • 6.2 partitioning of key-value data
    • 6.3 partitioning and secondary indexes
    • 6.4 rebalancing partitions
    • 6.5 request routing
  • 7 transactions
    • 7.1 the slippery concept of a transaction
    • 7.2 weak isolation levels
    • 7.3 serializability
  • 8 the trouble with distributed systems
    • 8.1 faults and partial failures
    • 8.2 unreliable networks
    • 8.3 unreliable clocks
    • 8.4 knowledge, truth and lies
  • 9 consistency and consensus
    • 9.1 consistency guarantees
    • 9.2 linearizability
    • 9.3 ordering guarantees
    • 9.4 distributed transactions and consensus
• III derived data
  • 10 batch processing
    • 10.1 batch processing with unix tools
    • 10.2 mapreduce and distributed filesystems
    • 10.3 beyond mapreduce
  • 11 stream processing
    • 11.1 transmitting event streams
    • 11.2 database and streams
    • 11.3 processing streams
  • 12 the future of data systems
    • 12.1 data integration
    • 12.2 unbundling databases
    • 12.3 aiming for correctness
    • 12.4 doing the right thing

Guide To Reliable Distributed Systems

• I computing in the cloud
  • 1 introduction
  • 2 the way of the cloud
  • 3 client perspective
  • 4 network perspective
  • 5 the structure of cloud data centers
  • 6 remote procedure calls and the client/server model
  • 7 corba: the common object request broker architecture
  • 8 system support for fast client/server communication
• II reliable distributed computing
  • 9 how and why computer systems fail
  • 10 overcoming failures in a distributed system
  • 11 dynamic membership
  • 12 group communication systems
  • 13 point to point and multi-group considerations
  • 14 the virtual synchrony execution model
  • 15 consistency in distributed systems
• III applications of reliability techniques
  • 16 retrofitting reliability into complex systems
  • 17 software architectures for group communication
• IV related technologies
  • 18 security options for distributed settings
  • 19 clock synchronization and synchronization systems
  • 20 transactional systems
  • 21 peer-to-peer systems and probabilistic protocols
  • 22 appendix A: virtualy synchronous methodology for building dynamic reliable services
  • 23 appendix B: isis API

Protocol Design

• 1 introduction
  • 1.1 what is a protocol?
  • 1.2 protocols as processes
  • 1.3 techniques for actual proofs
  • 1.4 real protocols
  • 1.5 readers's guide
• 2 CSP descriptions and proof rules
  • 2.1 processes and process synchronization
  • 2.2 channel history semantics
  • 2.3 failure semantics
• 3 protocols and services
  • 3.1 providing a service
  • 3.2 service features
  • 3.3 OSI and other layered architectures
• 4 basic protocol mechanisms
  • 4.1 sequence control and error control
  • 4.2 flow control
  • 4.3 indication of change of peer state
  • 4.4 change of service mode
  • 4.5 multiplexing and splitting
  • 4.6 segmentation and reassembly
  • 4.7 prioritisation
• 5 multi-peer consensus
  • 5.1 reliable consensus
  • 5.2 election
  • 5.3 commitment
  • 5.4 byzantine agreement
  • 5.5 clock synchronization
  • 5.6 finding the global state
• 6 security
  • 6.1 cryptographic methods
  • 6.2 integrity
  • 6.3 digital signatures
  • 6.4 entity authentication
  • 6.5 key exchange
  • 6.6 non-cryptographic methods
• 7 naming addressing and routing
  • 7.1 general principles of naming and addressing
  • 7.2 addressing structures
  • 7.3 routing
  • 7.4 congestion
• 8 protocol encoding
  • 8.1 simple binary encoding
  • 8.2 TLV encoding
  • 8.3 ASN.1 encoding
  • 8.4 ASCII encodings
• 9 protocols in the OSI lower layers
  • 9.1 data link layer
  • 9.2 network layer
  • 9.3 transport layer
• 10 application support protocols
  • 10.1 session layer
  • 10.2 presentation layer
  • 10.3 application layer
  • 10.4 basic application service elements
  • 10.5 commitment, concurrency and recovery
  • 10.6 client-server systems
  • 10.7 security middleware
• 11 application protocols
  • 11.1 file transfer
  • 11.2 distributed transaction processing
  • 11.3 message handling
  • 11.4 hypertext and the world wide web
  • 11.5 web services
• A notation
  • A.1 data types and variables
  • A.2 data values and expressions
  • A.3 processes and process expressions
  • A.4 traces, failures, and transitions
  • A.5 inference rules for process specifications
  • A.6 security
• B standarization
  • B.1 standards organizations
  • B.2 standards documents

Introduction to Reliable and Secure Distributed Programming (Carlos Varela, Cachin)

• 1 introduction
  • 1.1 motivation
  • 1.2 distributed programming abstractions
  • 1.3 the end-to-end argument
  • 1.4 software components
  • 1.5 classes of algorithms
• 2 basic abstractions
  • 2.1 distributed computation
  • 2.2 abstracting processes
  • 2.3 cryptographics abstractions
  • 2.4 abstracting communication
  • 2.5 timing assumptions
  • 2.6 abstracting time
  • 2.7 distributed system models
• 3 reliable broadcast
  • 3.1 motivation
  • 3.2 best-effort broadcast
  • 3.3 regular reliable broadcast
  • 3.4 uniform reliable broadcast
  • 3.5 stubborn broadcast
  • 3.6 logged best-effort broadcast
  • 3.7 logged uniform reliable broadcast
  • 3.8 probabilistic broadcast
  • 3.9 FIFO and causal broadcast
  • 3.10 byzantine consistent broadcast
  • 3.11 byzantine reliable broadcast
  • 3.12 byzantine broadcast channels
• 4 shared memory
  • 4.1 introduction
  • 4.2 (1,N) regular register
  • 4.3 (1,N) atomic register
  • 4.4 (N,N) atomic register
  • 4.5 (1,N) logged regular register
  • 4.6 (1,N) byzantine safe register
  • 4.7 (1,N) byzantine regular register
  • 4.8 (1,N) byzantine atomic register
• 5 consensus
  • 5.1 regular consensus
  • 5.2 uniform consensus
  • 5.3 uniform consensus in the fail-noisy model
  • 5.4 logged consensus
  • 5.5 randomized consensus
  • 5.6 byzantine consensus
  • 5.7 byzantine randomized consensus
• 6 consensus variants
  • 6.1 total-order broadcast
  • 6.2 byzantine total order broadcast
  • 6.3 terminating reliable broadcast
  • 6.4 fast consensus
  • 6.5 fast byzantine consensus
  • 6.6 nonblocking atomic commit
  • 6.7 group membership
  • 6.8 view-synchronous communication
• 7 concluding remarks
  • 7.1 implementation in appia
  • 7.2 further implementations
  • 7.3 further reading

Distributed Systems Principles and Paradigms (Tanenbaum)

• 1 introduction
  • 1.1 definition of distributed system
  • 1.2 goals
  • 1.3 types of distributed systems
• 2 architectures
  • 2.1 architectural styles
  • 2.2 system architectures
  • 2.3 architectures versus middleware
  • 2.4 self-management in distributed systems
• 3 processes
  • 3.1 threads
  • 3.2 virtualization
  • 3.3 clients
  • 3.4 servers
  • 3.5 code migration
• 4 communication
  • 4.1 fundamentals
  • 4.2 remote procedure call
  • 4.3 message-oriented communication
  • 4.4 stream-oriented communication
  • 4.5 multicast communication
• 5 naming
  • 5.1 names, identifiers and addresses
  • 5.2 flat naming
  • 5.3 structured naming
  • 5.4 attribute-based naming
• 6 synchronization
  • 6.1 clock synchronization
  • 6.2 logical clocks
  • 6.3 mutual exlusion
  • 6.4 global positioning of nodes
  • 6.5 election algorithms
• 7 consistency and replication
  • 7.1 introduction
  • 7.2 data-centric consistency models
  • 7.3 client-centric consistency models
  • 7.4 replica management
  • 7.5 consistency protocols
• 8 fault tolerance
  • 8.1 introduction to fault tolerance
  • 8.2 process resilience
  • 8.3 reliable client-server communication
  • 8.4 reliable group communication
  • 8.5 distributed commit
  • 8.6 recovery
• 9 security
  • 9.1 introduction to security
  • 9.2 secure channels
  • 9.3 access control
  • 9.4 security management
• 10 distributed object-based systems
  • 10.1 architecture
  • 10.2 processes
  • 10.3 communication
  • 10.4 naming
  • 10.5 synchronization
  • 10.6 consistency and replication
  • 10.7 fault tolerance
  • 10.8 security
• 11 distributed file systems
  • 11.1 architecture
  • 11.2 processes
  • 11.3 communication
  • 11.4 naming
  • 11.5 synchronization
  • 11.6 consistency and replication
  • 11.7 fault tolerance
  • 11.8 security
• 12 distributed web-based systems
  • 12.1 architecture
  • 12.2 processes
  • 12.3 communication
  • 12.4 naming
  • 12.5 synchronization
  • 12.6 consistency and replication
  • 12.7 fault tolerance
  • 12.8 security
• 13 distributed coordination-based systems
  • 13.1 introduction to coordination models
  • 13.2 architectures
  • 13.3 processes
  • 13.4 communication
  • 13.5 naming
  • 13.6 synchronization
  • 13.7 consistency and replication
  • 13.8 fault tolerance
  • 13.9 security
• 14 suggestions for further reading and bibliography

Distributed Systems: Concepts and Design (Colouris)

• 1 characterization of distributed systems
  • 1.1 introduction
  • 1.2 examples of distributed systems
  • 1.3 trends in distributed systems
  • 1.4 focus on resource sharing
  • 1.5 challenges
  • 1.6 case study: the world wide web
• 2 system models
  • 2.1 introduction
  • 2.2 physical models
  • 2.3 architectural models
  • 2.4 fundamental models
• 3 networking and internetworking
  • 3.1 introduction
  • 3.2 types of network
  • 3.3 network principles
  • 3.4 internet protocols
  • 3.5 case studies: ethernet, wifi and bluetooth
• 4 interprocess communication
  • 4.1 introduction
  • 4.2 the api for the internet protocols
  • 4.3 external data representation and marshalling
  • 4.4 multicast communication
  • 4.5 network virtualization: overlay networks
  • 4.6 case study: MPI
• 5 remote invocation
  • 5.1 introduction
  • 5.2 request-reply protocols
  • 5.3 remote procedure call
  • 5.4 remote procedure invocation
  • 5.5 case study: java RMI
• 6 indirect communication
  • 6.1 introduction
  • 6.2 group communication
  • 6.3 publish-subscribe systems
  • 6.4 message queues
  • 6.5 shared memory approaches
• 7 operating systems support
  • 7.1 introduction
  • 7.2 the operating system layer
  • 7.3 protection
  • 7.4 processes and threads
  • 7.5 communication and invocation
  • 7.6 operating system architecture
  • 7.7 virtualization at the operating system level
• 8 distributed objects and components
  • 8.1 introduction
  • 8.2 distributed objects
  • 8.3 case study: CORBA
  • 8.4 from objects to components
  • 8.5 case studies: enterprise javabeans and fractal
• 9 web services
  • 9.1 introduction
  • 9.2 web services
  • 9.3 service descriptions and IDL for web services
  • 9.4 a directory service for use with web services
  • 9.5 XML security
  • 9.6 coordination of web services
  • 9.7 applications of web services
• 10 peer-to-peer systems
  • 10.1 introduction
  • 10.2 napster and its legacy
  • 10.3 peer-to-peer middleware
  • 10.4 routing overlays
  • 10.5 overlay case studies: pastry, tapestry
  • 10.6 application case studies: squirrel, oceanstore, ivy
• 11 security
  • 11.1 introduction
  • 11.2 overview of security techniques
  • 11.3 digital signatures
  • 11.4 cryptography pragmatics
  • 11.6 case studies: needham-schroeder, kerberos, tls, 802.11 wifi
• 12 distributed file systems
  • 12.1 introduction
  • 12.2 file service architecture
  • 12.3 case study: sun network file system
  • 12.4 case study: the andrew file system
  • 12.5 enhancements and further developments
• 13 name services
  • 13.1 introduction
  • 13.2 name services and the domain name system
  • 13.3 directory services
  • 13.5 case study: the X.500 directory service
• 14 time and global states
  • 14.1 introduction
  • 14.2 clocks, events and process states
  • 14.3 synchronizing physical clocks
  • 14.4 logical time and logical clocks
  • 14.5 global states
  • 14.6 distributed debugging
• 15 coordination and agreement
  • 15.1 introduction
  • 15.2 distributed mutual exclusion
  • 15.3 elections
  • 15.4 coordination and agreement in group communication
  • 15.5 consensus and related problems

Distributed Operating Systems (Tanenbaum)

• 1 introduction to distributed systems
  • 1.1 what is a distributed system?
  • 1.2 goals
  • 1.3 hardware concepts
  • 1.4 software concepts
  • 1.5 design issues
• 2 communication in distributed systems
  • 2.1 layered protocols
  • 2.2 asynchronous transfer mode networks
  • 2.3 the client-server model
  • 2.4 remote procedure call
  • 2.5 group communication
• 3 synchronization in distributed systems
  • 3.1 clock synchronization
  • 3.2 mutual exclusion
  • 3.3 election algorithms
  • 3.4 atomic transactions
  • 3.5 deadlocks in distributed systems
• 4 processes and processors in distributed systems
  • 4.1 threads
  • 4.2 system models
  • 4.3 processor allocation
  • 4.4 scheduling in distributed systems
  • 4.5 fault tolerance
  • 4.6 real-time distributed systems
• 5 distributed file systems
  • 5.1 distributed file system design
  • 5.2 distributed file system implementation
  • 5.3 trends in distributed file systems
• 6 distributed shared memory
  • 6.1 introduction
  • 6.2 what is shared memory?
  • 6.3 consistency models
  • 6.4 paged-based distributed shared memory
  • 6.5 shared-variable distributed shared memory
  • 6.6 object-based distributed shared memory
  • 6.7 comparison
• 7 case study 1: amoeba
  • 7.1 introduction to amoeba
  • 7.2 objects and capabilities in amoeba
  • 7.3 process management in amoeba
  • 7.4 memory management in amoeba
  • 7.5 communication in amoeba
  • 7.6 the amoeba servers
• 8 case study 2: mach
  • 8.1 introduction to mach
  • 8.2 process management in mach
  • 8.3 memory management in mach
  • 8.4 communication in mach
  • 8.5 unix emulation in mach
• 9 case study 3: chorus
  • 9.1 introduction to chorus
  • 9.2 process management in chorus
  • 9.3 memory management in chorus
  • 9.4 communication in chorus
  • 9.5 unix emulation in chorus
  • 9.6 cool: an object oriented subsystem
  • 9.7 comparison of amoeba, mach and chorus
• 10 case study 4: DCE
  • 10.1 introduction to DCE
  • 10.2 threads
  • 10.3 remote procedure call
  • 10.4 time service
  • 10.5 directory service
  • 10.6 security service
  • 10.7 distributed file system

Distributed Operating Systems: Theory and Practice (lamport)

• 1 formal aspects of concurrent systems
  • 1.1 a formal basis for the specification of concurrent systems
  • 1.2 on the construction of distributed programs
  • 1.3 derivation of distributed algorithms
• 2 design issues for distributed systems
  • 2.1 design of highly decentralised operating systems
  • 2.2 communication models for distributed computation
  • 2.3 new concepts for distributed system structuring
• 3 hardware support for distributed computing systems
  • 3.1 distributed computing system architectures: hardware
  • 3.2 hardware support for the distributed operating system of the heidelberg polyp processor
• 4 case studies
  • 4.1 the apollo domain distributed file system
  • 4.2 the chorus distributed operating system: some design issues
  • 4.3 the conic support environment for distributed systems
  • 4.4 an experience in solving a transactions ordering problem in a distributed system
  • 4.5 distributed transaction processing and the camelot system
  • 4.6 work programs

Distributed Algorithms (Lynch)

• I synchronous network algorithms
  • 1 introduction
  • 2 modelling 1: synchronous network model
  • 3 leader election in a synchronous ring
  • 4 algorithms in general synchronous networks
  • 5 distributed consensus with link failures
  • 6 distributed consensus with process failures
  • 7 more consensus problems
• II asynchronous algorithms
  • 8 modelling 2: asynchronous system model
• IIA asynchronous shared memory algorithms
  • 9 modelling 3: asynchronous shared memory model
  • 10 mutual exclusion
  • 11 resource allocation
  • 12 consensus
  • 13 atomic objects
• IIB asynchronous network algorithms
  • 14 modelling 4: asynchronous network model
  • 15 basic asynchronous network algorithms
  • 16 synchronizers
  • 17 shared memory versus networks
  • 18 logical time
  • 19 global snapshots and stable properties
  • 20 network resource allocation
  • 21 asynchronous network with process failures
  • 22 data link protocols
• III partially synchronous algorithms
  • 23 partially synchronous system models
  • 24 mutual exlusion with partial synchrony
  • 25 consensus with partial synchrony

Distributed Algorithms for Message-Passing Systems (raynal)

• I distributed graph algorithms
  • 1 basic definitions and network traversal algorithms
  • 2 dsitributed graph algorithms
  • 3 an algorithmic framework to compute global functions on a process graph
  • 4 leader election algorithms
  • 5 mobile objects navigating a network
• II logical time and global states in distributed systems
  • 6 nature of distributed computations and the concept of a global state
  • 7 logical time in asynchronous distributed systems
  • 8 asynchronous distributed checkpointing
  • 9 simulating synchrony on top of asynchronous systems
• III mutual exclusion and resource allocation
  • 10 permission-based mutual exclusion algorithms
  • 11 distributed resource allocation
• IV high-level communication abstractions
  • 12 order constraints on message delivery
  • 13 rendezvous (synchronous) communication
• V detection properties on distributed executions
  • 14 distributed termination detection
  • 15 distributed deadlock detection
• VI distributed shared memory
  • 16 atomic consistency (linearizability)
  • 17 sequential consistency
  • 18 afterword

Distributed Systems An Algorithmic Approach (Ghosh)

• I background materials
  • 1 introduction
    • 1.1 what is a distributed system
    • 1.2 why distributed systems
    • 1.3 examples of distributed systems
    • 1.4 important issues in distributed systems
    • 1.5 common subproblems
    • 1.6 implementing a distributed system
    • 1.7 parallel versus distributed systems
  • 2 interprocess communication: an overview
    • 2.1 introduction
    • 2.2 network protocols
    • 2.3 naming
    • 2.4 remote procedure call
    • 2.5 remote method invocation
    • 2.6 messages
    • 2.7 web services
    • 2.8 event notification
    • 2.9 virtualization: cloud computing
    • 2.10 mobile agents
    • 2.11 basic group communication services
    • 2.12 concluding remarks
• II foundational topics
  • 3 models for communication
    • 3.1 need for a model
    • 3.2 message-passing model for interprocess communication
    • 3.3 shared variables
    • 3.4 modeling mobile agents
    • 3.5 relationship among models
    • 3.6 classification based on special properties
    • 3.7 complexity measures
    • 3.8 concluding remarks
  • 4 representing distributed algorithms: syntax and semantics
    • 4.1 introduction
    • 4.2 guarded actions
    • 4.3 nondeterminism
    • 4.4 atomic operations
    • 4.5 fairness
    • 4.6 central versus distributed schedulers
    • 4.7 concluding remarks
  • 5 program correctness
    • 5.1 introduction
    • 5.2 correctness criteria
    • 5.3 correctness proofs
    • 5.4 assertional reasoning: proving safety priorities
    • 5.5 proving liveness properties using well-founded sets
    • 5.6 programming logic
    • 5.7 predicate transformers
    • 5.8 concluding remarks
  • 6 time in a distributed system
    • 6.1 introduction
    • 6.2 logical clocks
    • 6.3 vector clocks
    • 6.4 physical clock synchronization
    • 6.5 concluding remarks
• III important paradigms
  • 7 mutual exclusion
    • 7.1 introduction
    • 7.2 solutions on message-passing systems
    • 7.3 token-passing algorithms
    • 7.4 solutions on the shared-memory model
    • 7.5 mutual exclusion using special instructions
    • 7.6 group mutual exclusion
    • 7.7 concluding remarks
  • 8 distributed snapshot
    • 8.1 introduction
    • 8.2 properties of consisten snapshots
    • 8.3 chandy-lamport algorithm
    • 8.4 lai-yang algorithm
    • 8.5 distributed debugging
    • 8.6 concluding remarks
  • 9 global state collection
    • 9.1 introduction
    • 9.2 elementary algorithm for all-to-all broadcasting
    • 9.3 termination-detection algorithms
    • 9.4 wave algorithms
    • 9.5 distributed deadlock detection
    • 9.6 concluding remarks
  • 10 graph algorithms
    • 10.1 introduction
    • 10.2 routing algorithms
    • 10.3 graph traversal
    • 10.4 graph coloring
    • 10.5 cole-vishkin reduction algorithm for tree coloring
    • 10.6 maximal independent set: luby's algorithm
    • 10.7 concluding remarks
  • 11 coordination algorithms
    • 11.1 introduction
    • 11.2 leader election
    • 11.3 synchronizers
    • 11.4 concluding remarks
• IV faults and fault-tolerant systems
  • 12 fault-tolerant systems
    • 12.1 introduction
    • 12.2 classification of faults
    • 12.3 specification of faults
    • 12.4 fault-tolerant systems
    • 12.5 tolerating crash failures
    • 12.6 tolerating omission failures
    • 12.7 concluding remarks
  • 13 distributed consensus
    • 13.1 introduction
    • 13.2 consensus in asynchronous systems
    • 13.3 consensus in synchronous systems: byzantine generals problem
    • 13.4 paxos algorithm
    • 13.5 failure detectors
    • 13.6 concluding remarks
  • 14 distributed transactions
    • 14.1 introduction
    • 14.2 classification of transactions
    • 14.3 implementing transactions
    • 14.4 concurrency control and serializability
    • 14.5 atomic commit protocols
    • 14.6 recovery from failures
    • 14.7 conclusing remarks
  • 15 group communication
    • 15.1 introduction
    • 15.2 atomic multicast
    • 15.3 ip multicast
    • 15.4 application layer multicast
    • 15.5 ordered multicasts
    • 15.6 reliable multicast
    • 15.7 open groups
    • 15.8 overview of transis
    • 15.9 concluding remarks
  • 16 replicated data management
    • 16.1 introduction
    • 16.2 architecture of replicated data management
    • 16.3 data-centric consistency tools
    • 16.4 client-centric consistency protocols
    • 16.5 implementation of data-centric consistency models
    • 16.6 quorum-based protcols
    • 16.7 replica placement
    • 16.8 brewer's cap theorem
    • 16.9 case studies
    • 16.10 concluding remarks
  • 17 self-stabilizing systems
    • 17.1 introduction
    • 17.2 theoretical foundation
    • 17.3 stabilizing mutual exclusion
    • 17.4 stabilizing graph coloring
    • 17.5 stabilizing spanning tree protocol
    • 17.6 stabilizing maximal matching
    • 17.7 distributed reset
    • 17.8 stabilizing clock phase synchronization
    • 17.9 concluding remarks
• V real-world issues
  • 18 distributed discrete-event simulation
    • 18.1 introduction
    • 18.2 distributed simulation
    • 18.3 conservative simulation
    • 18.4 optimistic simulation and time warp
    • 18.5 concluding remarks
  • 19 security in distributed systems
    • 19.1 introduction
    • 19.2 security mechanisms
    • 19.3 common security attacks
    • 19.4 encryption
    • 19.5 secret key cryptosystem
    • 19.6 public key cryptosystems
    • 19.7 digital signatures
    • 19.8 hashing algorithms
    • 19.9 elliptic curve cryptography
    • 19.10 authentication server
    • 19.11 digital certificates
    • 19.12 case studies
    • 19.13 virtual private networks and firewalls
    • 19.14 sharing a secret
    • 19.15 concluding remarks
  • 20 sensor networks
    • 20.1 vision
    • 20.2 architecture of sensor nodes
    • 20.3 challenges in wireless sensor networks
    • 20.4 routing algorithms
    • 20.5 time synchronization using reference broadcast
    • 20.6 localization algorithms
    • 20.7 security in sensor networks
    • 20.8 applications
    • 20.9 concluding remarks
  • 21 social and peer-to-peer networks
    • 21.1 introduction to social networks
    • 21.2 metrics of social networks
    • 21.3 modeling socail networks
    • 21.4 centrality measures in social networks
    • 21.5 community detection
    • 21.6 introduction to peer-to-peer networks
    • 21.7 first-generation p2p systems
    • 21.8 second-generation p2p systems
    • 21.9 koorde and de bruijn graph
    • 21.10 skip graph
    • 21.11 replication management
    • 21.12 bittorrent and free riding
    • 21.13 censorship resistance, anonimity
    • 21.14 concluding remarks

Distributed Systems An Intuitive Approach (Wan Fokkink)

• I message passing
  • 1 introduction
  • 2 preliminaries
  • 3 snapshots
  • 4 waves
  • 5 deadlock detection
  • 6 terminatino detection
  • 7 garbage collection
  • 8 routing
  • 9 election
  • 10 anonymous networks
  • 11 synchronous networks
  • 12 crash failures
  • 13 byzantine failures
  • 14 mutual exlusion
• II shared memory
  • 15 preliminaries
  • 16 mutual exclusion II
  • 17 barriers
  • 18 self-stabilization
  • 19 online scheduling

Notes on Theory of Distributed Systems

• I message passing
  • 1 introduction
  • 2 model
  • 3 coordinated attack
  • 4 broadcast and convergecast
  • 5 distributed breadth-first search
  • 6 leader election
  • 7 synchronous agreement
  • 8 byzantine agreement
  • 9 impossibility of asynchronous agreement
  • 10 paxos
  • 11 failure detectors
  • 12 logical clocks
  • 13 synchronizers
  • 14 quorum systems
• II shared memory
  • 15 model
  • 16 distributed shared memory
  • 17 mutual exclusion
  • 18 the wait-free hiararchy
  • 19 atomic snapshots
  • 20 lower bounds on perturbable objects
  • 21 restricted-use objects
  • 22 common2
  • 23 randomized consensus and test-and-set
  • 24 renaming
  • 25 software transactional memory
  • 26 obstruction-freedom
  • 27 BG simulation
  • 28 topological methods
  • 29 approximate agreement

Scaling Reliably: Improving the Scalability of the Erlang Distributed Actor Platform

• 1 INTRODUCTION Controlling shared state is the only way to build reliable scalable systems. State shared by multiple units of computation limits scalability due to high synchronisation and communication costs. Moreover, shared state is a threat for reliability as failures corrupting or permanently locking shared state may poison the entire system. To facilitate the development of scalable Erlang systems and make them maintainable, we have developed three new tools—Devo, SDMon, and WombatOAM—and enhanced two others—the visualisation tool Percept and the refactorer Wrangler.
• 2 CONTEXT
  • 2.1 Scalable Reliable Programming Models
  • 2.2 Actor Languages
  • 2.3 Erlang’s Support for Concurrency
  • 2.4 Scalability and Reliability in Erlang Systems
  • 2.5 ETS: Erlang Term Storage
• 3 BENCHMARKS FOR SCALABILITY AND RELIABILITY
  • 3.1 Orbit
  • 3.2 Ant Colony Optimisation (ACO)
• 4 ERLANG SCALABILITY LIMITS
  • 4.1 Scaling Erlang on a Single Host
  • 4.2 Distributed Erlang Scalability
  • 4.3 Persistent Storage
• 5 IMPROVING LANGUAGE SCALABILITY
  • 5.1 SD Erlang Design
  • 5.2 S_group Semantics
  • 5.3 Semantics Validation
• 6 IMPROVING VM SCALABILITY
  • 6.1 Improvements to Erlang Term Storage
  • 6.2 Improvements to Schedulers
  • 6.3 Improvements to Time Management
• 7 SCALABLE TOOLS
  • 7.1 Refactoring for Scalability
  • 7.2 Scalable Deployment
  • 7.3 Monitoring and Visualisation
• 8 SYSTEMIC EVALUATION
  • 8.1 Orbit
  • 8.2 Ant Colony Optimisation (ACO)
  • 8.3 Evaluation Summary
• 9 DISCUSSION
• APPENDIX: ARCHITECTURE SPECIFICATIONS

Microservices

⚠️ WIP ⚠️

Observability

⚠️ WIP ⚠️

• Books

Books

Programming Languages

Ada

Array Languages

The BEAM Ecosystem

Table of Contents

• Erlang
• Elixir
• Gleam
• Other

Erlang

Elixir

Gleam

Other

C

C++

Go

Haskell

Idris

LISP

• Online Resources
• Racket
• Books
  • Basics & General - Common Lisp
    • Common Lisp. A Gentle Introduction to Symbolic Computation [David Touretzky]
    • Practical Common Lisp [Peter Seibel]
    • Land of Lisp [Conrad Barski]
    • ANSI Common Lisp [Paul Graham]
    • Common Lisp the Language [Guy Steele]
  • Basics & General - Scheme
    • Structure and Interpretation of Computer Programs [Guy Steele]
    • The Little Schemer
  • Other
    • Common Lisp. An interactive approach [Stuart Shapiro]
    • Loving Lisp
    • Successful Lisp
    • The Art of Lisp Programming
  • Advanced & Metaprogramming
    • Object-Oriented Programming in Common Lisp
    • The Art of Metaobject Protocol
    • On Lisp
    • Let over Lambda
    • Paradigms of Artificial Intelligence

Online Resources

Racket

• RacketCon

• 2020/11 Rebuilding the Racket Compiler with Chez Scheme

• 2019/07 Racket is an acceptable Python

• 2022/02 Why learn Racket? A student's perspective

Books

Basics & General - Common Lisp

Common Lisp. A Gentle Introduction to Symbolic Computation [David Touretzky]

Practical Common Lisp [Peter Seibel]

Land of Lisp [Conrad Barski]

ANSI Common Lisp [Paul Graham]

Common Lisp the Language [Guy Steele]

Basics & General - Scheme

Structure and Interpretation of Computer Programs [Guy Steele]

The Little Schemer

Other

Common Lisp. An interactive approach [Stuart Shapiro]

Loving Lisp

Successful Lisp

The Art of Lisp Programming

Advanced & Metaprogramming

Object-Oriented Programming in Common Lisp

The Art of Metaobject Protocol

On Lisp

Let over Lambda

Paradigms of Artificial Intelligence

The Bipolar Lisp Programmer

Having programmed in or around Lisp for nearly 20 years now, and
spectated a lot of Usenet postings and blogs written by Lisp
programmers, I have often wondered if there was such a thing as a 'Lisp
character', in the same way that groups and nations have a national
character.

After some thought, I decided there was definitely a Lisp profile
amongst the people using the language and that this character was
responsible for some of the interesting history of this language and its
peculiar strengths and weaknesses.

So here is an essay which will no doubt annoy several and lead to
argument.  Its called

The Bipolar Lisp Programmer

Any lecturer who serves his time will probably graduate hundreds, if not
thousands of students.  Mostly they merge into a blur; like those
paintings of crowd scenes where the leading faces are clearly picked out
and the rest just have iconic representations.   This anonymity can be
embarrassing when some past student hails you by name and you really
haven't got the foggiest idea of who he or she is.  It's both nice to be
remembered and also toe curlingly embarrassing to admit that you cannot
recognise who you are talking to.

But some faces you do remember; students who did a project under you.
Also two other categories - the very good and the very bad.   Brilliance
and abject failure both stick in the mind. And one of the oddest things,
and really why I'm writing this short essay, is that there are some
students who actually fall into both camps.  Here's another confession.
I've always liked these students and had a strong sympathy for them.

Now abject failure is nothing new in life.  Quite often I've had
students who have failed miserably for no other reason than they had
very little ability.    This is nothing new. What is new is that in the
UK, we now graduate a lot of students like that.  But, hey, that's
a different story and I'm not going down that route.

No I want to look at the brilliant failures.   Because brilliance amd
failure are so often mixed together and our initial reaction is it
shouldn't be.   But it happens and it happens a lot.  Why?

Well, to understand that, we have to go back before university. Let's go
back to high school and look at a brilliant failure in the making.
Those of you who have seen the film "Donnie Darko" will know exactly the
kind of student I'm talking about.  But if you haven't, don't worry,
because you'll soon recognise the kind of person I'm talking about.
Almost every high school has one every other year or so.

Generally what we're talking about here is a student of outstanding
brilliance.  Someone who is used to acing most of his assignments; of
doing things at the last minute but still doing pretty well at them.
At some level he doesn't take the whole shebang all that seriously;
because, when you get down to it, a lot of the rules at school are
pretty damned stupid.  In fact a lot of the things in our world don't
make a lot of sense, if you really look at them with a fresh mind.  

So we have two aspects to this guy; intellectual acuteness and not
taking things seriously.  The not taking things seriously goes with
finding it all pretty easy and a bit dull.  But also it goes with
realising that a lot of human activity is really pretty pointless, and
when you realise that and internalise it then you become cynical and
also a bit sad - because you yourself are caught up in this machine and
you have to play along if you want to get on.  Teenagers are really good
at spotting this kind of phony nonsense.  Its also the seed of an
illness; a melancholia that can deepen in later life into full blown
depression.

Another feature about this guy is his low threshold of boredom. He'll
pick up on a task and work frantically at it, accomplishing wonders in
a short time and then get bored and drop it before its properly
finished.  He'll do nothing but strum his guitar and lie around in bed
for several days after. That's also part of the pattern too; periods of
frenetic activity followed by periods of melancholia, withdrawal and
inactivity.   This is a bipolar personality.

Alright so far?  OK, well lets graduate this guy and see him go to
university.  What happens to him then?

Here we have two stories; a light story and a dark one.

The light story is that he's really turned on by what he chooses and he
goes on to graduate summa cum laude, vindicating his natural brilliance.

But that's not the story I want to look at.  I want to look at the dark
story.  The one where brilliance and failure get mixed together.

This is where this student begins by recognising that university, like
school, is also fairly phony in many ways. What saves university is
generally the beauty of the subject as built by great minds.  But if you
just look at the professors and don't see past their narrow obsession
with their pointless and largely unread (and unreadable) publications to
the great invisible university of the mind, you will probably conclude
its as phony as anything else.  Which it is.

But lets stick to this guy's story.

Now the big difference between school and university for the fresher is
FREEDOM.  Freedom from mom and dad, freedom to do your own thing.
Freedom in fact to screw up in a major way.   So our hero begins a new
life and finds he can do all he wants.  Get drunk, stumble in at 3.00
AM. So he goes to town and he relies on his natural brilliance to carry
him through because, hey, it worked at school.  And it does work for
a time.

But brilliance is not enough.  You need application too, because the
material is harder at university.   So pretty soon our man is getting
B+, then Bs and then Cs for his assignments.   He experiences
alternating feelings of failure cutting through his usual self
assurance.  He can still stay up to 5.00AM and hand in his assignment
before the 9.00AM deadline, but what he hands in is not so great.  Or
perhaps he doesn't get into beer, but into some mental digression from
his official studies that takes him too far away from the main syllabus.

This sort of student used to pass my way every now and then, riding on
the bottom of the class.   One of them had Bored> as his UNIX prompt. If
I spotted one I used to connect well with them.  (In fact I rescued one
and now he's a professor and miserable because he's surrounded by
phonies - but hey, what can you do?).   Generally he would come alive in
the final year project when he could do his own thing and hand in
something really really good.   Something that would show (shock,
horror) originality.  And a lot of professors wouldn't give it a fair
mark for that very reason - and because the student was known to be
scraping along the bottom.

Often this kind of student never makes it to the end.  He flunks himself
by dropping out.   He ends on a soda fountain or doing yard work, but
all the time reading and studying because a good mind is always hungry.

Now one of the things about Lisp, and I've seen it before, is that Lisp
is a real magnet for this kind of mind.   Once you understand that, and
see that it is this kind of mind that has contributed a lot to the
culture of Lisp, you begin to see why Lisp is, like many of its
proponents, a brilliant failure.  It shares the peculiar strengths and
weaknesses of the brilliant bipolar mind (BBM).

Why is this?  Well, its partly to do with vision.   The 'vision thing'
as George Bush Snr. once described it, is really one of the strengths of
the BBM.  He can see far; further than in fact his strength allows him
to travel.  He conceives of brilliant ambitious projects requiring great
resources, and he embarks on them only to run out of steam.  It's not
that he's lazy; its just that his resources are insufficient.

And this is where Lisp comes in.  Because Lisp, as a tool, is to the
mind as the lever is to the arm.  It amplifies your power and enables
you to embark on projects beyond the scope of lesser languages like C.
Writing in C is like building a mosaic out of lentils using a tweezer
and glue.   Lisp is like wielding an air gun with power and precision.
It opens out whole kingdoms shut to other programmers.

So BBMs love Lisp.  And the stunning originality of Lisp is reflective
of the creativity of the BBM; so we have a long list of ideas that
originated with Lispers - garbage collection, list handling, personal
computing, windowing and areas in which Lisp people were amongst the
earliest pioneers.  So we would think, off the cuff, that Lisp should be
well established, the premiere programming language because hey - its
great and we were the first guys to do this stuff.

But it isn't and the reasons why not are not in the language, but in the
community itself, which contains not just the strengths but also the
weaknesses of the BBM.

One of these is the inability to finish things off properly.  The phrase
'throw-away design' is absolutely made for the BBM and it comes from the
Lisp community.   Lisp allows you to just chuck things off so easily,
and it is easy to take this for granted.  I saw this 10 years ago when
looking for a GUI to my Lisp (Garnet had just gone West then).  No
problem, there were 9 different offerings.  The trouble was that none of
the 9 were properly documented and none were bug free. Basically each
person had implemented his own solution and it worked for him so that
was fine.   This is a BBM attitude; it works for me and I understand it.
It is also the product of not needing or wanting anybody else's help to
do something.

Now in contrast, the C/C++ approach is quite different.  It's so damn
hard to do anything with tweezers and glue that anything significant you
do will be a real achievement.  You want to document it.  Also you're
liable to need help in any C project of significant size; so you're
liable to be social and work with others.   You need to, just to get
somewhere.

And all that, from the point of view of an employer, is attractive. Ten
people who communicate, document things properly and work together are
preferable to one BBM hacking Lisp who can only be replaced by another
BBM (if you can find one) in the not unlikely event that he will, at
some time, go down without being rebootable.

Now the other aspect of the BBM that I remarked on is his sensitivity to
artifice.  To put it in plain American, he knows bullshit when he smells
it.   Most of us do.  However the BBM has much lower tolerance of it
than others.  He can often see the absurdity of the way things are, and
has the intelligence to see how they should be.  And he is, unlike the
rank and file, unprepared to compromise.  And this leads to many things.

The Lisp machines were a product of this kind of vision. It was, as
Gabriel once said, the Right Thing.  Except of course it wasn't.  Here
the refusal to compromise with the market, and to use the platforms that
the C bashers were using proved in the long run to be a fatal mistake.

And this brings me to the last feature of the BBM.  The flip side of all
that energy and intelligence - the sadness, melancholia and loss of self
during a down phase.    If you read many posts discussing Lisp
(including one in comp.lang.lisp called Common Lisp Sucks) you see it
writ large.   Veteran programmers of many years with obvious ability and
talent go down with a fit of the blues.  The intelligence is directed
inwards in mournful contemplation of the inadequacies of their favourite
programming language.   The problems are soluble (Qi is a proof of that
for God's sake), but when you're down everything seems insoluble.  Lisp
is doomed and we're all going to hell.

Actually one paper that exemplifies that more than any other is the
classic Lisp: Good News, Bad News, How to Win Big. If you read that
paper, you feel and see nature of the BBM.  Its unique because Gabriel
actually displays both aspects at the same time.   The positive side,
the intellectual pride and belief in Lisp is there.  But also in there
is the depressive 'but its all going to go to hell' aspect is there too.
This is contained in the message that Worse is Better.

So what's the message in all of this? Basically, that there are two
problems. The problem with the Lisp mindset and the problem with Lisp.
The problem of the Lisp mindset is the problem of the mindset
characteristic of the BBM.

And the problem with Lisp?  The answer is tailor made for the minds who
program it. It is the koan of Lisp.

The answer is that there is no problem with Lisp, because Lisp is, like
life, what you make of it.  

The Lisp Curse

by Rudolf Winestock

This essay is yet another attempt to reconcile the power of the Lisp
programming language with the inability of the Lisp community to
reproduce their pre-AI Winter achievements. Without doubt, Lisp has been
an influential source of ideas even during its time of retreat. That
fact, plus the brilliance of the different Lisp Machine architectures,
and the current Lisp renaissance after more than a decade in the
wilderness demonstrate that Lisp partisans must have some justification
for their smugness. Nevertheless, they have not been able to translate
the power of Lisp into a movement with overpowering momentum.

In this essay, I argue that Lisp's expressive power is actually a cause
of its lack of momentum.

The power of Lisp is its own worst enemy.

Here's a thought experiment to prove it: Take two programming languages,
neither of which are object-oriented. Your mission, if you choose to
accept it, is to make them object-oriented, keeping them
backward-compatible with the original languages, modulo some edge cases.
Inserting any pair of programming languages into this thought experiment
will show that this is easier with some languages than with others.
That's the point of the thought experiment. Here's a trivial example:
Intercal and Pascal.

Now make this thought experiment interesting: Imagine adding object
orientation to the C and Scheme programming languages. Making Scheme
object-oriented is a sophomore homework assignment. On the other hand,
adding object orientation to C requires the programming chops of Bjarne
Stroustrup.

The consequences of this divergence in needed talent and effort cause
The Lisp Curse:

Lisp is so powerful that problems which are technical issues in other
programming languages are social issues in Lisp.

Consider the case of Scheme, again. Since making Scheme object-oriented
is so easy, many Scheme hackers have done so. More to the point, many
individual Scheme hackers have done so. In the 1990s, this led to
a veritable warehouse inventory list of object-oriented packages for the
language. The Paradox of Choice, alone, guaranteed that none of them
would become standard. Now that some Scheme implementations have their
own object orientation facilities, it's not so bad. Nevertheless, the
fact that many of these packages were the work of lone individuals led
to problems which Olin Shivers wrote about in documenting the Scheme
Shell, scsh.

Programs written by individual hackers tend to follow the
scratch-an-itch model. These programs will solve the problem that the
hacker, himself, is having without necessarily handling related parts of
the problem which would make the program more useful to others.
Furthermore, the program is sure to work on that lone hacker's own
setup, but may not be portable to other Scheme implementations or to the
same Scheme implementation on other platforms. Documentation may be
lacking. Being essentially a project done in the hacker's copious free
time, the program is liable to suffer should real-life responsibilities
intrude on the hacker. As Olin Shivers noted, this means that these
one-man-band projects tend to solve eighty-percent of the problem.

Dr. Mark Tarver's essay, The Bipolar Lisp Programmer, has an apt
description of this phenomenon. He writes of these lone-wolf Lisp
hackers and their

...inability to finish things off properly. The phrase 'throw-away
design' is absolutely made for the BBM and it comes from the Lisp
community. Lisp allows you to just chuck things off so easily, and it is
easy to take this for granted. I saw this 10 years ago when looking for
a GUI to my Lisp. No problem, there were 9 different offerings. The
trouble was that none of the 9 were properly documented and none were
bug free. Basically each person had implemented his own solution and it
worked for him so that was fine. This is a BBM attitude; it works for me
and I understand it. It is also the product of not needing or wanting
anybody else's help to do something.

Once again, consider the C programming language in that thought
experiment. Due to the difficulty of making C object oriented, only two
serious attempts at the problem have made any traction: C++ and
Objective-C. Objective-C is most popular on the Macintosh, while C++
rules everywhere else. That means that, for a given platform, the
question of which object-oriented extension of C to use has already been
answered definitively. That means that the object-orientated facilities
for those languages have been documented, that integrated development
environments are aware of them, that code libraries are compatible
with them, and so forth.

Dr. Mark Tarver's essay on bipolar Lispers makes the point:

Now in contrast, the C/C++ approach is quite different. It's so damn
hard to do anything with tweezers and glue that anything significant you
do will be a real achievement. You want to document it. Also you're
liable to need help in any C project of significant size; so you're
liable to be social and work with others. You need to, just to get
somewhere.

And all that, from the point of view of an employer, is attractive. Ten
people who communicate, document things properly and work together are
preferable to one BBM hacking Lisp who can only be replaced by another
BBM (if you can find one) in the not unlikely event that he will, at
some time, go down without being rebootable.

Therefore, those who already know C don't ask "What object system should
I learn?" Instead, they use C++ or Objective-C depending on what their
colleagues are using, then move on to "How do I use object-oriented
feature X?" Answer: "Goog it and ye shall find."

Real Hackers, of course, have long known that object-oriented
programming is not the panacea that its partisans have claimed. Real
Hackers have moved on to more advanced concepts such as immutable data
structures, type inferencing, lazy evaluation, monads, arrows, pattern
matching, constraint-based programming, and so forth. Real Hackers have
also known, for a while, that C and C++ are not appropriate for most
programs that don't need to do arbitrary bit-fiddling. Nevertheless, the
Lisp Curse still holds.

Some smug Lisp-lovers have surveyed the current crop of academic
languages (Haskell, Ocaml, et cetera) and found them wanting, saying
that any feature of theirs is either already present in Lisp or can be
easily implemented — and improved upon — with Lisp macros. They're
probably right.

Pity the Lisp hackers.

Dr. Mark Tarver — twice-quoted, above — wrote a dialect of Lisp called
Qi. It is less than ten thousand lines of macros running atop Clisp. It
implements most of the unique features of Haskell and OCaml. In some
respects, Qi surpasses them. For instance, Qi's type inferencing engine
is Turing complete. In a world where teams of talented academics were
needed to write Haskell, one man, Dr. Tarver wrote Qi all by his
lonesome.

Read that paragraph, again, and extrapolate.

Exercise for the reader: Imagine that a strong rivalry develops between
Haskell and Common Lisp. What happens next?

Answer: The Lisp Curse kicks in. Every second or third serious Lisp
hacker will roll his own implementation of lazy evaluation, functional
purity, arrows, pattern matching, type inferencing, and the rest. Most
of these projects will be lone-wolf operations. Thus, they will have
eighty percent of the features that most people need (a different eighty
percent in each case). They will be poorly documented. They will not be
portable across Lisp systems. Some will show great promise before being
abandoned while the project maintainer goes off to pay his bills.
Several will beat Haskell along this or that dimension (again,
a different one in each case), but their acceptance will be hampered by
flame wars on the comp.lang.lisp Usenet group.

Endgame: A random old-time Lisp hacker's collection of macros will add
up to an undocumented, unportable, bug-ridden implementation of 80% of
Haskell because Lisp is more powerful than Haskell.

The moral of this story is that secondary and tertiary effects matter.
Technology not only affects what we can do with respect to technological
issues, it also affects our social behavior. This social behavior can
loop back and affect the original technological issues under
consideration.

Lisp is a painfully eloquent exemplar of this lesson. Lisp is so
powerful, that it encourages individual independence to the point of
bloody-mindedness. This independence has produced stunningly good
innovation as in the Lisp Machine days. This same independence also
hampers efforts to revive the "Lisp all the way down" systems of old; no
"Lisp OS" project has gathered critical mass since the demise of
Symbolics and LMI.

One result of these secondary and tertiary effects is that, even if Lisp
is the most expressive language ever, such that it is theoretically
impossible to make a more expressive language, Lispers will still have
things to learn from other programming languages. The Smalltalk guys
taught everyone — including Lisp hackers — a thing or two about object
oriented programming. The Clean programming language and the Mozart/Oz
combo may have a few surprises of their own.

The Lisp Curse does not contradict the maxim of Stanislav Datskovskiy:
Employers much prefer that workers be fungible, rather than maximally
productive. Too true. With great difficulty does anyone plumb the
venality of the managerial class. However, the last lines of his essay
are problematic. To wit:

As for the “free software” world, it eagerly opposes industrial dogmas
in rhetoric but not at all in practice. No concept shunned by cube farm
hells has ever gained real traction among the amateur masses.

In a footnote, he offers Linux as an example of this unwillingness to
pursue different ideas. To be sure, he has a point when it comes to
operating systems (the topmost comment, in particular, is infuriatingly
obtuse). He does not have a point when it comes to programming
languages. Python and Ruby were influenced by Lisp. Many of their fans
express respect for Lisp and some of their interest has augmented the
Lisp renaissance. With some justice, JavaScript has been described as
"Scheme in C's clothing" despite originating in those cube farm hells.

Nevertheless, in spite of this influence, in both the corporate and open
source worlds, Lisp still has only a fraction of the developer mind
share which the current crop of advanced scripting languages have
attracted. The closed-mindedness of MBA's cannot be the only explanation
for this. The Lisp Curse has more explanatory power.

The free development environments available for Lisp further exemplify
the Lisp Curse.

It's embarrassing to point this out, but it must be done. Forget about
the Lisp Machine; we don't even have development systems that match what
the average Smalltalk hacker takes for granted ("I've always felt Lisp
is the superior language and Smalltalk is the superior environment."
- Ramon Leon). Unless they pay thousands of dollars, Lisp hackers are
still stuck with Emacs.

James Gosling, the author of the first Emacs that ran on Unix, has
correctly pointed out that Emacs has not fundamentally changed in more
than twenty years. This is because the Emacs maintainers are still
layering code atop a design which was settled back when Emacs was
a grad-student project at the MIT AI Lab, i.e., when Emacs development
was still being indirectly financed by the national debt. A Slashdotter
may object that Emacs is already quite capable and can do anything that
any other development environment can do, only better. Those who have
used Lisp Machines say otherwise.

So why don't the Lisp hackers put the Smalltalk guys in their proper
place? Why don't they make a free development system that calls to mind
some of the lost glories of the LispM, even if they can't reproduce
another LispM?

The reason why this doesn't happen is because of the Lisp Curse. Large
numbers of Lisp hackers would have to cooperate with each other. Look
more closely: Large numbers of the kind of people who become Lisp
hackers would have to cooperate with each other. And they would have to
cooperate with each other on a design which was not already a given from
the beginning. And there wouldn't be any external discipline, such as
a venture capitalist or other corporate master, to keep them on track.

Every project has friction between members, disagreements, conflicts
over style and philosophy. These social problems are counter-acted by
the fact that no large project can be accomplished otherwise. "We must
all hang together, or we will all hang separately." But the
expressiveness of Lisp makes this countervailing force much weaker; one
can always start one's own project. Thus, individual hackers decide that
the trouble isn't worth it. So they either quit the project, or don't
join the project to begin with. This is the Lisp Curse.

One could even hack Emacs to get something that's good enough. Thus, the
Lisp Curse is the ally of Worse is Better.

The expressive power of Lisp has drawbacks. There is no such thing as
a free lunch.

Racket

Scheme

Common Lisp

Python

Rust

• Learning
• The language & its features
  • Rust vs Other Languages
  • Ownership
  • Concurrency
  • Async/Await
    • Tokio
  • Unsafe
  • Macros
• Error Handling
  • Reddit
• Testing
  • Fuzzing
• Coverage
• Development Tools
  • Editors
    • VS Code
    • Xi
    • Helix
    • Lapce
    • Zed
  • Cargo
  • Rust Analyzer
• Debugging
  • GDB
  • LLDB
  • RR
  • RD
• Observability
  • Logging
    • Simple minimal loggers
    • Complex configurable frameworks
      • slog
      • tracing.rs
    • Adaptors for other facilities
    • For WebAssembly binaries
    • For embedded systems
  • Metrics
    • NewRelic
    • DataDog
  • Distributed Tracing
    • OpenTracing
    • OpenTelemetry
    • Jaeger
    • Zipkin
    • Honeycomb.io
• Performance Engineering
  • Profiling
    • Causal Profiling
  • Performance Optimization
• Command Line Applications
  • CLI Applications written in Rust
  • Argument Parsing
  • Input
  • Output
  • Error Handling
  • Other
• Configuration Management
• Interop
  • Serializing/Deserializing
    • Serde
  • Porting from C to Rust
  • C
  • Erlang & Elixir
  • Python
• Algorithms
  • Combinatorics
  • Sorting
  • Searching
  • Hashing
  • Judy Arrays
  • Graphs
  • Evaluation Graphs
  • Probabilistic Data Structures
  • State Machines
• Entity Component Systems
  • SPECS
  • Legion
  • hecs
  • Bevy ECS
• Games
  • Amethyst
  • GGEZ
  • Piston
  • Bevy
  • Rapier
  • Roguelikes
• Graphics
  • Nannou
• User Interfaces
  • Druid
• Storage & Data Bases
  • Sled
  • TiKV
  • TiDB
  • Noria
  • Apache Arrow
  • Timely & Differential Dataflow
• Text Search
  • Tantivy
  • Sonic
  • Meilisearch
• Operating Systems
  • TockOS
  • Redox
• Cloud
  • AWS
• Embedded
• Cross Compiling
• Programming Language Technology
  • Parsing
    • LARLPop
    • Nom
    • Menhir
    • Pratt Parsers
    • Chumsky
    • Tree Sitter
  • LLVM
  • Rustc Compiler
    • Rust Compilation Speed
  • Cranelift
  • GCC-Rust
• Notes

Learning

• This Week In Rust
• Read Rust
• A half-hour to learn Rust
• The Rust Programming Language Book
• Comprehensive Rust
• Rust by Example
• The Rust Cookbook
• Into Rust
• Rust-101
• Rust 101, tutorial de Rust en español
• Learn Rust: A Resource Guide
• Ferrous Systems' Elements of Rust
• play.org Rust
• 2020 Rust Starter Kit
• Learn Rust With Entirely Too Many Linked Lists
• JavaPoint Rust Tutorial
• How to Get Started With Rust
• Easy Rust
• Tour of Rust
• Rustlings
  • 2021/06 The Rustlings exercises - part 1
• Exercism
• Learning Rust
• Ferrous Systems: Learning Rust
• Ferrous Systems: Learning Rust: Mindsets and Expectations
• Ferrous Systems: Learning Rust: OMG WTF RS – resources to help you get started with Rust
• Learn Rust With Benford's Law
• Easy Rust
• PingCap
  • PingCap Talent Plan
  • TinyKV
  • TinySQL
• Awesome Rust
• rust-learning
• cheats.rs
• ralfbiedert/cheats.rs
• Rust Quizhttps://github.com/dtolnay/rust-quiz
• Can I use...
• ferrous-systems / teaching-material
• Rust from 0 to 80% for JavaScript Developers
• Rust by Practice
• Effective Rust - 35 Specific Ways to Improve Your Rust Code

The language & its features

• 2013/05/01 Go and Rust — objects without class
• 2013/07/03 Philosophy and "for" loops — more from Go and Rust
• 2014/12/21 Rust, an Anti-Sloppy Programming Language
• 2015/09/28 When Rust Makes Sense, or The State of Typed Languages
• 2016/09/01 IRLO: Setting our vision for the 2017 cycle
• 2016/10/07 Type-Safe Unions in C++ and Rust
• 2016/12/21 Four years with Rust
• 2017/12/21 Rust in 2017: what we achieved
• 2018/01/03 My journey with Rust in 2017 — The good, the bad, the weird
• 2018/01/13 Rust in 2018: it's way easier to use!
• 2018/07/27 What is Rust 2018?
• 2018/12/06 Rust 2018 is here… but what is it?
• 2018/12/08 The Fallow Year, my Rust2019 post
• 2018/12/28 Thoughts on Rust in 2019
• 2019/01/01 Rust in 2019
• 2019/01/04 r/rust Rust 2019: Beat C++
• 2019/01/07 Rust in 2019: Focus on sustainability
• 2019/01/12 Rust 2019: Solid Foundations for Unsafe Code
• 2020-10-05 The Rust 2021 Experience - Year of the Macro
• 2020/09/03 Planning the 2021 Roadmap
• 2020/09/05 Joshua Nelson: Rust in 2021
• 2020/09/08 mark-i-m: Rust 2021
• 2020/09/08 Nick Cameron: Rust in 2021
• 2020/09/10 Ivan Tham: Rust 2021
• 2020/09/12 Aleksey Kladov: Rust in 2021 r/rust
• 2020/09/13 Henri Sivonen: Rust 2021
• 2020/09/17 Krishna Sundarram: Rust 2021: Lower the barriers
• 2020/09/21 Llogiq: Rust 2021 – Ethical Development
• 2020/09/28 Raph Levien: Rust 2021: GUI r/rust HN
• 2020/10/05 Rust 2021: Foundation
• 2021/10/15 xampprocky: Rust 2021: Sustainability

Rust vs Other Languages

• 2013 Benchmarks Round Two: Parallel Go, Rust, D, Scala and Nimrod
• 2015 Why Go and Rust are not competitors
• 2015 A Quick Comparison of Nim vs. Rust
• 2016 Rust vs C Pitfalls
• 2017 Rust vs. Go
• 2018 Should C Programmers learn C++, Go or Rust?
• 2018 The success of Go heralds that of Rust
• 2019 One Program Written in Python, Go, and Rust
• 2019 Why Go and not Rust?
• 2020 Rust & Python — A Gentle Comparison using Simple Neural Networks
• 2020 Rust vs Go
• 2020 Early Impressions of Rust from a Go Programmer
• 2020 Go vs Rust: Writing a CLI tool
• 2020 Go vs Rust: Which is Better Programming Language for Future and Why?
• 2020 Why Discord is switching from Go to Rust
• 2020 Pros and Cons of Rust and Go
• 2020 Assorted thoughts on zig (and rust)

Ownership

• 2014 Rust Means Never Having to Close a Socket
• 2014 How to think about Rust ownership versus C++ unique_ptr
• 2014 Rust lifetimes: Getting away with things that would be reckless in C++
• 2015 Rust – memory safety without garbage collector
• 2015 Rust, Ownership, and Iteration
• 2015 Understanding Pointers, Ownership, and Lifetimes in Rust
• 2015 Rust Data Ownership
• 2016 Rust's ownership and borrowing in 150 words
• 2016 Understanding Rust: ownership, borrowing, lifetimes
• 2016 Why Rust's ownership/borrowing is hard
• 2016 Rust's Ownership Model
• 2016 Moving, Cloning, and Copying Coloring Books in Rust
• 2016 into_rust() Why Rust?
• 2016 into_rust(Hello, world!)
• 2016 into_rust() Ownership
• 2016 into_rust() Shared borrows
• 2016 into_rust() Mutable borrows
• 2016 Learn You a Rust for Great Good!
• 2016 Learn You a Rust II - References and Borrowing
• 2016 Learn You a Rust III - Lifetimes 101
• 2016 Learn You a Rust IV - Lifetime Fenangling
• 2016 Tricks with ownership in Rust
• 2017/01/22 Short intro to C++ for Rust developers: Ownership and Borrowing
• 2017 Graphical depiction of ownership and borrowing in Rust
• 2017 Ownership and Borrowingand Lifetimes (Oh My!)
• 2017 What's a reference in Rust?
• 2017 Strategies for Returning References in Rust
• 2017 Racking Your Brain with Rust
• 2018 Ownership in Rust, Part 1
• 2018 Ownership in Rust, Part 2
• 2018 Ownership Explained with Python
• 2018 Ownership in the Rust Language
• 2018 Basics of Ownership: Rust Crash Course Lesson 2, Part 1
• 2018 Fear not the Rust Borrow Checker
• 2018 Rust Design Considerations with Borrowing
• 2018 Ownership & Borrowing
• 2018 Move Semantics vs Copy Semantics
• 2018 MIR-based borrow check (NLL) status update
• 2018 The Concept of Ownership in Rust andSwift
• 2018 Moves and Borrowing In Rust With Jim Blandy
• 2018 Rust Lifetimes for the Uninitialised
• 2018 How to Use Rust Non Lexical Lifetimes on Nightly
• 2019 Understanding Rust Lifetimes
• 2019 Memory Management in Rust: Ownership
• 2019 Rust ownership, the hard way
• 2019 Rust: The Hard Parts - Part One
• 2019 Here be (owned) books
• 2019 Breaking News: Non-Lexical Lifetimes Arrives for Everyone
• 2019 The Power of Lifetimes
• 2020 The Fatal Flaw of Ownership Semantics
• 2021 Understanding ownership in Rust
• 2022/04 The Rust Borrow Checker - a Deep Dive
  • HN
• 2022/08 Borrow is not a pointer

Concurrency

• 2015 Fearless Concurrency with Rust
• 2017 Multithreading in Rust with MPSC (Multi-Producer, Single Consumer) channels
• 2017 Implementing cooperative multitasking in Rust
• 2017 on mutex performance and WTF::Lock
• 2018 A Rusty Go at Channels
• 2019 Rust parallelism for non-C/C++ developers
• 2019 Rust concurrency patterns: regretless concurrency?
• 2019 Lock-free Rust: Crossbeam in 2019
  • HN
• 2020 Concurrency Patterns in Embedded Rust
• 2022 Rust Concurrency Cheat Sheet
  • r/
• 2022/05 Arc and Mutex in Rust

Async/Await

• Asynchronous Programming in Rust
• Are We Async Yet?
• RFC 2394 async/wait
• 2016 Zero-cost futures in Rust · Aaron Turon
• 2018 Async Methods I: generic associated types
• 2018 Async Methods II: object safety
• 2018 Async/Await I: Self-Referential Structs
• 2018 Async/Await II: Narrowing the Scope of the Problem
• 2018 Async/Await III: Moving Forward with Something Shippable
• 2018 Async/Await IV: An Even Better Proposal
• 2018 Async/Await V: Getting back to the futures
• 2018 Async/Await VI: 6 weeks of great progress
• 2018 Async & Await in Rust: a full proposal
• 2019 Asynchronous Destructors
• 2019 Async-await status report
• 2019 Async-await status report #2
• 2019 why async fn in traits are hard
• 2019 Announcing the Async Interviews
  • Async Interview #1: Alex and Nick talk about async I/O and WebAssembly
  • Async Interview #2: cramertj
  • Async Interview #2: cramertj, part 2
  • Async Interview #2: cramertj, part 3
  • Async Interview #3: Carl Lerche
  • Async Interview #4: Florian Gilcher
  • Async Interview #5: Steven Fackler
  • Async Interview #6: Eliza Weisman
  • Async Interview #7: Withoutboats
  • Async Interview #8: Stjepan Glavina
  • Async interviews: my take thus far
• 2018 Inside Rust's Async Transform
• 2018 Hexilee/async-io-demo
• 2019 How Rust optimizes async/await I
• 2019 How Rust optimizes async/await II
• 2020 async/await on embedded Rust
• 2019 Explained: How does async work in Rust?
• 2019 Explained: Futures in Rust for Web Development
• 2019 Reddit: Is await only useful is my code doesn't do much itself?
• 2019 Async Stack Traces in Rust
• 2019 Stop worrying about blocking: the new async-std runtime, inspired by Go
• 2019 Streams Concurrency
• 2019 Async-await on stable Rust!
• 2019 Announcing Rust 1.39.0
• 2020 A practical guide to async in Rust
• 2020 I'm not feeling the async pressure
• 2020 Surviving Rust async interfaces
• 2020 Futures Explained in 200 Lines of Rust
  • HN
• 2022/03 Async destructors, async genericity and completion futures
• 2022/06 (async) Rust doesn't have to be hard
• 2022/06 Local Async Executors and Why They Should be the Default

Tokio

• Tokio.rs
• Tokio Tutorial
• Tokio Blog
  • 2018 A great 2018, an even better 2019
  • 2020 Reducing tail latencies with automatic cooperative task yielding
  • 2020 Announcing Tokio 1.0
• 2018 What Are Tokio and Async IO All About?
• 2019 tokio ain’t for mere mortals
• 2019 Using TLS in RustGetting async I/O with tokio, second try

Unsafe

• Rust's Unsafe Code Guidelines Reference
• The Rustonomicon
• unsaferust.org
• 2016 The Scope of Unsafe
• 2017 Undefined vs Unsafe in Rust
• 2018 Unsafe Abstractions
• 2018 You can't "turn off the borrow checker" in Rust
• 2021 An unsafe tour of Rust's Send and Sync

Macros

• A Practical Intro to Macros in Rust 1.0
• The Little Book of Rust Macros
• cargo-expand
• 2016 Things you could do with the Rust AST
• 2017 An Overview of Macros in Rust
• 2017 My first Rust macro
• 2017 Abstracting over mutability in Rust macros
• 2018 Rust Blog: Procedural Macros in Rust 2018
  • r/
• 2018 Why Rust Has Macros
• 2018 The Case For Macros
• 2018 Program Synthesis is Possible in Rust
• 2018/12 IRLO Procedural Macros book
• 2019 A Love Letter to Rust Macros
• 2019 Deriving Traits in Rust with Procedural Macros
• 2019 6 useful Rust macros that you might not have seen before
• 2019 Reddit: Rust macros are amazing. I recently ran into a profound limitation of C++ at my job trying to apply an operation to a collection of identifiers

Error Handling

• anyhow This library provides anyhow::Error, a trait object based error type for easy idiomatic error handling in Rust applications.
  • eyre This library provides eyre::Report, a trait object based error handling type for easy idiomatic error handling and reporting in Rust applications. This crate is a fork of anyhow with a support for customized error reports. For more details on customization checkout the docs on eyre::EyreHandler.
  • simple-eyre This library provides a custom eyre::EyreHandler type for usage with eyre that provides a minimal error report with no additional context. Essentially the minimal implementation of an error reporter.
  • stable-eyre This library provides a custom eyre::EyreHandler type for usage with eyre that provides all the same features as eyre::DefaultHandler except it works on stable by capturing a backtrace::Backtrace via backtrace-rs.
• thiserror This library provides a convenient derive macro for the standard library's std::error::Error trait.
• adhocerr A library for the construction of efficient single use static/dynamic error types per callsite.
• extracterr Helpers for bundling context with errors and later extracting said context thru dyn Error trait objects. The primary purpose of this crate is to pass context to error reporters through dyn Error trait objects. This is useful for information that may need to be captured by leaf errors but which doesn't belong in any single error's message. Backtraces, http status codes, and help messages are all examples of context that one might wish to pass directly to an error reporter rather than printing in the chain of errors.
• quick-error A macro which makes error types pleasant to write.
• failure deprecated
• Rust traits for iterator of Option and Result
• The Rust Programming Language Book: Chapter 9 Error Handling
• Rust Cookbook - Error Handling
• Rust By Example - Error handling
• Microsoft Training - Take your first steps in Rust - Handle errors in Rust
• Ferrous Systems Teaching Material - Error Handling
• Effective Rust Item 3: Avoid matching Option and Result
• Effective Rust Item 4: Prefer idiomatic Error variants
• Result and Option map
• 2014/10/16 On Error Handling in Rust
• 2014/11/06 Improved Error Handling in Rust
• 2015/05/14 Error Handling in Rust — Andrew Gallant's Blog
• 2016/01/28 Rust: The ? operator · m4rw3r
• 2016/11/30 Starting a new Rust project right, with error-chain
• 2018/04/20 Why Rust's error handling is awesome
• 2018/12/06 RUST : ERROR HANDLING
• 2019/11/13 Error Handling Survey
• 2019/11/14 Thoughts on Error Handling in Rust
• 2020/04/05 My private take on error handling in Rust
• 2020/04/08 Error Handling in a Correctness-Critical Rust Project r/
• 2020/04/16 Unwrap and Expect in Rust
• 2020/05/06 Rust Error Handling
• 2020/05/13 Rust: Structuring and handling errors in 2020 r/
• 2020/06/05 Taking the Unhappy Path with Result, Option, unwrap and ? operator in Rust
• 2020/06/15 Understanding Memory and Thread Safety Practices and Issues in Real-World Rust Programs r/ r/
• 2020/08/02 Beginner's guide to Error Handling in Rust
• 2020/08/16 Rust Error Handling | How to Define Generic Error Types?
• 2020/09/08 As a hobbyist rust developer, I want to think less about error handling
• 2020/09/18 Announcing the Error Handling Project Group
• 2020/09/18 Announcing the Error Handling Project Group
• 2020/10/18 Building Your Own Error Type: Part 1
• 2020/11/18 Anonymous Sum Types for Rust Error Handling
• 2020/11/23 What the Error Handling Project Group is Working On
• 2020/11/30 Error handling is hard
• 2021/01/24 Wrapping Errors in Rust
• 2021/04/04 Unwrapping Options and Results: Part 1
• 2021/04/06 A Beginner's Guide to Handling Errors in Rust
• 2021/05/13 Error Handling In Rust - A Deep Dive
• 2021/07/01 What the Error Handling Project Group is Working Towards
• 2021/07/18 Geeks for Geeks - Rust Error Handling
• 2021/09/07 Error handling in Rust
• 2021/12/13 Rust Error Handling
• 2022/01/16 Outcomes, Mistakes, and the Nuance of Error Handling HN
• 2022/01/16 Rust Error Handling, Part One
• 2022/01/17 Rust Error Handling, Part Two
• 2022/01/31 Rust Linz, January '22 - Error Handling in Rust - A Pragmatic Approach by Luca Palmieri
• 2022/02/08 The simplest guide to error handling in Rust
• 2022/03/27 Handling Errors in Rust
• 2022/04/01 Understanding Rust Option and Result enums
• 2022/04/06 Rusty shorts -(Option, Result)
• 2022/05/06 Beginner-Intermediate Rust Error Handling r/
• 2022/05/23 Crash reporting in Rust
• 2022/06/30 More than you've ever wanted to know about errors in Rust r/
• 2022/07/01 Simple error handling in Rust r/rust
• 2022/07/14 Why Rust should not have provided unwrap r/
• 2022/08/08 Using unwrap() in Rust is Okay
• 2022/09/14 Rust Error Handling
• 2023/04/08 Modular Errors in Rust r/