Peter Norvig's Lis.py

Here are my notes from Peter Norvig's excellent Lisp Interpreter article. You should definitely read through his post and write your own Lisp interpreter as you go. It only takes about an hour and is quite enlightening.

---

• Alan Kay calls it [the Lisp Interpreter written in Lisp] Maxwell's Equations of Software.
• As Steve Yegge said, "If you don't know how compilers work, then you don't know how computers work."
• The syntax of a language is the arrangement of characters to form correct statements or expressions; the semantics is the meaning of those statements or expressions.
• We say we are evaluating an expression when we determine its value.
• Scheme syntax:
• Scheme programs consist solely of expressions. There is no statement/expression distinction.
• Numbers and symbols are called atomic expressions; they cannot be broken into pieces.
• Everything else is a list expression.
• The beauty of Scheme is that the full language only needs 5 keywords and 8 syntactic forms.
• A language interpreter has two parts: parsing and execution.
• The parsing component takes an input program in the form of a sequence of characters, verifies it according to the syntactic rules of the language, and translates the program into an internal representation.
• The internal representation is then processed according to the semantic rules of the language, thereby carrying out the computation.
• program -> parser -> abstract syntax tree -> eval -> result
• In a simple interpreter the internal representation is a tree structure (often called an abstract syntax tree) that closely mirrors the nested structure of statements or expressions in the program.
• In a language translator called a compiler there is often a series of internal representations, starting with an abstract syntax tree, and progressing to a sequence of instructions that can be directly executed by the computer.
• Parsing is traditionally separated into two parts: lexical analysis, in which the input character string is broken up into a sequence of tokens, and syntactic analysis, in which the tokens are assembled into an abstract syntax tree.
• The function eval takes two arguments: an expression, x, that we want to evaluate, and an environment, env, in which to evaluate it.
• An environment is a mapping from variable names to their values.
• One of Lisp's great legacies is the notion of an interactive read-eval-print loop: a way for a programmer to enter an expression, and see it immediately read, evaluated, and printed, without having to go through a lengthy build/compile/run cycle.
• The lambda special form creates a procedure.
• When we look up a variable in a nested environment, we look first at the innermost level, but if we don't find the variable name there, we move to the next outer level.
• The process of looking first in inner environments and then in outer ones is called lexical scoping.
• Scheme manages to do without these [while and for loops] just fine.
• In Scheme you iterate by defining recursive functions.