Course Introduction

An interpreter is a program that takes as input a stream of characters, along with additional inputs (e.g., user-provided command line arguments) and produces the output value of the program represented by the input stream of characters, if the stream of characters does in fact represent a valid program; the interpreter may choose to report an error otherwise. There several steps to this process which make up the interpretation pipeline visualized in \Cref{fig:interp-pipe}. As we will come to understand it, an interpreter does four things:

\begin{enumerate} \item It attempts to convert the input stream of characters into a stream of \textit{tokens} by grouping together related characters. We think of tokens as the \textit{units} or \textit{atoms} of our programming langauge. This part interpretation is called \textbf{lexical analysis}, and its primary purpose is to simplify the process of analyzing the input program. It's useful, for example, to know whether the character \codel{1} that appears in our program is part of a number (e.g., \codel{210}) or a variable name (e.g., \codel{case1}). Lexical analysis handles all these low-level syntactic concerns up front. In analogy with natural language, this is akin to when your brain combines sequences of sounds or letters into whole words. \item The interpreter then attempts to convert the stream of tokens into an \textit{abstract syntax tree (AST)}, which is a representation of our program as \textit{hierarchical data}. This part of interpretation is called \textbf{syntactic analysis} or \textbf{parsing}. Hierarchical data is easier to analyze and evaluate, e.g., it's useful to know whether a variable \codel{x} that appear in our program is part of an arithmetic expression (e.g., \codel{x + 1}) or part of a new variable declaration (e.g., \codel{let x = 1}). In analogy with natural language, this is akin to when your brain combines words into sub-phrases like prepositional phrases and verb phrases. \item Not all programs we can write make sense. It doesn't make sense, for example, to add a number to a string.\footnote{Even though some languages allow you to do this.} The next part of interpretation consists of analyzing an AST to verify that everything in it \enquote{looks reasonable}; this is generally called \textbf{static (semantic) analysis}. There are many forms of static analysis, but the one we'll focus on is \textbf{type checking}. Types help us describe what kind of things we're working with \textit{before we run our program}. They help us determine \textit{before we run our program} if we're using data correctly. In analogy with natural language, this is akin to the uneasy feeling you get when you hear or see a sentence like \enquote{the happiness is cold}; the word \enquote{happiness} isn't the right kind of word for its place in the sentence, despite the fact that the sentence is grammatically correct. Not all languages have type checkers, but we maintain that \enquote{good} languages have type checkers. \item Everything above is in service of \textit{running} our program. This part of interpretion is called \textbf{dynamic (semantic) analysis} or \textbf{evaluation}. This is the most intuitive part of an interpreter for programmers; learning to program is ultimately internalizing the evaluation rules of a programming language so that we know what to write to accomplish a certain task. \end{enumerate}

The above outline should be understood as our roadmap; we will consider each part in turn, and build several interpreters along the way. For each part, there will be two perspectives: the theoretical perspective and the practical perspective. For example, the formal counterpart of syntactic analysis is \textbf{formal grammar} and the practical counterpart is \textbf{parsing}. By the end we hope you'll have gained an appreciation for the considerations that go into designing \enquote{good} programming languages.