Why does this matter? As Steve Yegge said, "If you don't know how compilers work, then you don't know how computers work." Yegge describes 8 problems that can be solved with compilers (or equally with interpreters, or with Yegge's typical heavy dosage of cynicism).
Scheme syntax is different from most other languages you may be familiar with. Consider:
Java has a wide variety of syntactic conventions (keywords, infix operators, three kinds of brackets, operator precedence, dot notation, quotes, commas, semicolons), but Scheme syntax is much simpler:
Java Scheme if (x.val() > 0) {
fn(A[i] + 1,
return new String[] {"one", "two"});
}(if (> (val x) 0)
(fn (+ (aref A i) 1)
(quote (one two)))
In this page we will cover all the important points of Scheme (omitting some minor details), but we will take two steps to get there, defining a simplified language first, before defining the nearfull Scheme language.
(begin (define r 10) (* pi (* r r)))Here is a table of all the allowable expressions:
Expression  Syntax  Semantics and Example 

variable reference  var  A symbol is interpreted as a variable name;
its value is the variable's
value. Example: r ⇒ 10 (assuming r was previously defined to be 10) 
constant literal  number  A number
evaluates to itself. Examples: 12 ⇒ 12 or 3.45e+6 ⇒ 3.45e+6 
conditional  (if test conseq alt)  Evaluate test; if true,
evaluate and return conseq; otherwise
alt. Example: (if (> 10 20) (+ 1 1) (+ 3 3)) ⇒ 6 
definition  (define var exp)  Define a new variable and give it
the value of evaluating the expression exp.
Examples: (define r 10) 
procedure call  (proc arg...)  If proc is
anything other than one of the symbols if, define,
or quote then it is treated as a procedure. Evaluate proc
and all the args, and then the procedure is applied to the list of arg values. Example: (sqrt (* 2 8)) ⇒ 4.0 
In the Syntax column of this table, var must be a symbol, number must be an integer or floating point number, and the other italicized words can be any expression. The notation arg... means zero or more repetitions of arg.
program (str) ➡ parse ➡ abstract syntax tree (list) ➡ eval ➡ result (object)
And here is a short example of what we want parse and eval to be able to do:
>> program = "(begin (define r 10) (* pi (* r r)))" >>> parse(program) ['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]] >>> eval(parse(program)) 314.1592653589793
def tokenize(chars): "Convert a string of characters into a list of tokens." return chars.replace('(', ' ( ').replace(')', ' ) ').split()
>>> program = "(begin (define r 10) (* pi (* r r)))" >>> tokenize(program) ['(', 'begin', '(', 'define', 'r', '10', ')', '(', '*', 'pi', '(', '*', 'r', 'r', ')', ')', ')']
Our function parse will take a string representation of a program as input, call tokenize to get a list of tokens, and then call read_from_tokens to assemble an abstract syntax tree. read_from_tokens looks at the first token; if it is a ')' that's a syntax error. If it is a '(', then we start building up a list of subexpressions until we hit a matching ')'. Any nonparenthesis token must be a symbol or number. We'll let Python make the distinction between them: for each nonparen token, first try to interpret it as an int, then as a float, and finally as a symbol. Here is the parser:
def parse(program): "Read a Scheme expression from a string." return read_from_tokens(tokenize(program)) def read_from_tokens(tokens): "Read an expression from a sequence of tokens." if len(tokens) == 0: raise SyntaxError('unexpected EOF while reading') token = tokens.pop(0) if '(' == token: L = [] while tokens[0] != ')': L.append(read_from_tokens(tokens)) tokens.pop(0) # pop off ')' return L elif ')' == token: raise SyntaxError('unexpected )') else: return atom(token) def atom(token): "Numbers become numbers; every other token is a symbol." try: return int(token) except ValueError: try: return float(token) except ValueError: return Symbol(token)parse works like this:
>>> program = "(begin (define r 10) (* pi (* r r)))" >>> parse(program) ['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]We have made some choices about the representation of Scheme objects. Here we make the choices explicit:
Symbol = str # A Scheme Symbol is implemented as a Python str List = list # A Scheme List is implemented as a Python list Number = (int, float) # A Scheme Number is implemented as a Python int or floatWe're almost ready to define eval. But we need one more concept first.
import math imoort operator as op Env = dict # An environment is a mapping of {variable: value} def standard_env(): "An environment with some Scheme standard procedures." env = Env() env.update(vars(math)) # sin, cos, sqrt, pi, ... env.update({ '+':op.add, '':op.sub, '*':op.mul, '/':op.div, '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq, 'abs': abs, 'append': op.add, 'apply': apply, 'begin': lambda *x: x[1], 'car': lambda x: x[0], 'cdr': lambda x: x[1:], 'cons': lambda x,y: [x] + y, 'eq?': op.is_, 'equal?': op.eq, 'length': len, 'list': lambda *x: list(x), 'list?': lambda x: isinstance(x,list), 'map': map, 'max': max, 'min': min, 'not': op.not_, 'null?': lambda x: x == [], 'number?': lambda x: isinstance(x, Number), 'procedure?': callable, 'round': round, 'symbol?': lambda x: isinstance(x, Symbol), }) return env global_env = standard_env()
We are now ready for the implementation of eval. As a refresher, we repeat the table of Scheme forms:
Expression  Syntax  Semantics and Example 

variable reference  var  A symbol is interpreted as a variable name;
its value is the variable's
value. Example: r ⇒ 10 (assuming r was previously defined to be 10) 
constant literal  number  A number
evaluates to itself. Examples: 12 ⇒ 12 or 3.45e+6 ⇒ 3.45e+6 
conditional  (if test conseq alt)  Evaluate test; if true,
evaluate and return conseq; otherwise
alt. Example: (if (> 10 20) (+ 1 1) (+ 3 3)) ⇒ 6 
definition  (define var exp)  Define a new variable and give it
the value of evaluating the expression exp.
Examples: (define r 10) 
procedure call  (proc arg...)  If proc is
anything other than one of the symbols if, define,
or quote then it is treated as a procedure. Evaluate proc
and all the args, and then the procedure is applied to the list of arg values. Example: (sqrt (* 2 8)) ⇒ 4.0 
Notice how closely the code for eval follows the table:
def eval(x, env=global_env): "Evaluate an expression in an environment." if isinstance(x, Symbol): # variable reference return env[x] elif not isinstance(x, List): # constant literal return x elif x[0] == 'if': # conditional (_, test, conseq, alt) = x exp = (conseq if eval(test, env) else alt) return eval(exp, env) elif x[0] == 'define': # definition (_, var, exp) = x env[var] = eval(exp, env) else: # procedure call proc = eval(x[0], env) args = [eval(arg, env) for arg in x[1:]] return proc(*args)
We're done! You can see it all in action:
>>> eval(parse("(define r 10)")) >>> eval(parse("(* pi (* r r))")) 314.1592653589793
def repl(prompt='lis.py> '): "A promptreadevalprint loop." while True: val = eval(parse(raw_input(prompt))) if val is not None: print(schemestr(val)) def schemestr(exp): "Convert a Python object back into a Schemereadable string." if isinstance(exp, list): return '(' + ' '.join(map(schemestr, exp)) + ')' else: return str(exp)Here is repl in action:
>>> repl() lis.py> (define r 10) lis.py> (* pi (* r r)) 314.159265359 lis.py> (if (> (* 11 11) 120) (* 7 6) oops) 42 lis.py>
Expression  Syntax  Semantics and Example 

quotation  (quote exp) 
Return the exp literally; do not evaluate it. Example: (quote (+ 1 2)) ⇒ (+ 1 2) 
assignment  (set! var exp)  Evaluate exp and assign that value to
var, which must have been previously defined (with a
define or as a parameter to an enclosing procedure).
Example: (set! r2 (* r r)) 
procedure  (lambda (var...) exp)  Create a procedure
with parameter(s) named var... and exp as the body. Example: (lambda (r) (* pi (* r r))) 
The lambda special form (an obscure nomenclature choice that refers to Alonzo Church's lambda calculus) creates a procedure. We want procedures to work like this:
lis.py> (define circlearea (lambda (r) (* pi (* r r))) lis.py> (circlearea 10) 314.159265359The procedure call (circlearea 10) causes us to evaluate the body of the procedure, (* pi (* r r)), in an environment in which pi and * have the same global values they always did, but now r has the value 10. However, it wouldn't do to just set r to be 10 in the global environment. What if we were using r for some other purpose? We wouldn't want a call to circlearea to alter that value. Instead, we want to arrange for there to be a local variable named r that we can set to 10 without worrying about interfering with any other variable that happens to have the same name. We will create a new kind of environment, one which allows for both local and global variables.
The idea is that when we evaluate (circlearea 10), we will fetch the procedure body, (* pi (* r r)), and evaluate it in an environment that has r as the sole local variable, but also has access to the global environment. In other words, we want an environment that looks like this, with the local environment nested inside the "outer" global environment:
pi: 3.141592653589793
*: <builtin function mul> ...

When we look up a variable in such 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.
It is clear that procedures and environments are intertwined, so let's define them together:
class Procedure(object): "A userdefined Scheme procedure." def __init__(self, parms, body, env): self.parms, self.body, self.env = parms, body, env def __call__(self, *args): return eval(self.body, Env(self.parms, args, self.env)) class Env(dict): "An environment: a dict of {'var':val} pairs, with an outer Env." def __init__(self, parms=(), args=(), outer=None): self.update(zip(parms, args)) self.outer = outer def find(self, var): "Find the innermost Env where var appears." return self if (var in self) else self.outer.find(var) global_env = standard_env()We see that every procedure has three components: a list of parameter names, a body expression, and an environment that tells us what nonlocal variables are accessible from the body.
An environment is a subclass of dict, so it has all the methods that dict has. In addition there are two methods: the constructor __init__ builds a new environment by taking a list of parameter names and a corresponding list of argument values, and creating a new environment that has those {variable: value} pairs as the inner part, and also refers to the given outer environment. The method find is used to find the right environment for a variable: either the inner one or an outer one.
To see how these all go together, here is the new definition of eval. Note that the clause for variable reference has changed: we now have to call env.find(x) to find at what level the variable x exists; then we can fetch the value of x from that level. (The clause for define has not changed, because a define always adds a new variable to the innermost environment.) There are two new clauses: for set!, we find the environment level where the variable exists and set it to a new value. With lambda, we create a new procedure object with the given parameter list, body, and environment.
def eval(x, env=global_env): "Evaluate an expression in an environment." if isinstance(x, Symbol): # variable reference return env.find(x)[x] elif not isinstance(x, List): # constant literal return x elif x[0] == 'quote': # quotation (_, exp) = x return exp elif x[0] == 'if': # conditional (_, test, conseq, alt) = x exp = (conseq if eval(test, env) else alt) return eval(exp, env) elif x[0] == 'define': # definition (_, var, exp) = x env[var] = eval(exp, env) elif x[0] == 'set!': # assignment (_, var, exp) = x env.find(var)[var] = eval(exp, env) elif x[0] == 'lambda': # procedure (_, parms, body) = x return Procedure(parms, body, env) else: # procedure call proc = eval(x[0], env) args = [eval(arg, env) for arg in x[1:]] return proc(*args)
To appreciate how procedures and environments work together, consider this program and the environment that gets formed when we evaluate (account1 20.00):


Each rectangular box represents an environment, and the color of the box matches the color of the variables that are newly defined in the environment. In the last two lines of the program we define account1 and call (account1 20.00); this represents the creation of a bank account with a 100 dollar opening balance, followed by a 20 dollar withdrawal. In the process of evaluating (account1 20.00), we will eval the expression highlighted in yellow. There are three variables in that expression. amt can be found immediately in the innermost (green) environment. But balance is not defined there: we have to look at the green environment's outer env, the blue one. And finally, the variable + is not found in either of those; we need to do one more outer step, to the global (red) environment. This process of looking first in inner environments and then in outer ones is called lexical scoping. Env.find(var) finds the right environment according to lexical scoping rules.
Let's see what we can do now:
>>> repl() lis.py> (define circlearea (lambda (r) (* pi (* r r)))) lis.py> (circlearea 3) 28.274333877 lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact ( n 1)))))) lis.py> (fact 10) 3628800 lis.py> (fact 100) 9332621544394415268169923885626670049071596826438162146859296389521759999322991 5608941463976156518286253697920827223758251185210916864000000000000000000000000 lis.py> (circlearea (fact 10)) 4.1369087198e+13 lis.py> (define first car) lis.py> (define rest cdr) lis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0))) lis.py> (count 0 (list 0 1 2 3 0 0)) 3 lis.py> (count (quote the) (quote (the more the merrier the bigger the better))) 4 lis.py> (define twice (lambda (x) (* 2 x))) lis.py> (twice 5) 10 lis.py> (define repeat (lambda (f) (lambda (x) (f (f x))))) lis.py> ((repeat twice) 10) 40 lis.py> ((repeat (repeat twice)) 10) 160 lis.py> ((repeat (repeat (repeat twice))) 10) 2560 lis.py> ((repeat (repeat (repeat (repeat twice)))) 10) 655360 lis.py> (pow 2 16) 65536.0 lis.py> (define fib (lambda (n) (if (< n 2) 1 (+ (fib ( n 1)) (fib ( n 2)))))) lis.py> (define range (lambda (a b) (if (= a b) (quote ()) (cons a (range (+ a 1) b))))) lis.py> (range 0 10) (0 1 2 3 4 5 6 7 8 9) lis.py> (map fib (range 0 10)) (1 1 2 3 5 8 13 21 34 55) lis.py> (map fib (range 0 20)) (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)We now have a language with procedures, variables, conditionals (if), and sequential execution (the begin procedure). If you are familiar with other languages, you might think that a while or for loop would be needed, but Scheme manages to do without these just fine. The Scheme report says "Scheme demonstrates that a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language." In Scheme you iterate by defining recursive functions.
bash$ grep "^\s*[^#\s]" lis.py  wc 117 497 4276
From there Tony and I split paths. He reasoned that the hard part was the interpreter for expressions; he needed Lisp for that, but he knew how to write a tiny C routine for reading and echoing the nonLisp characters and link it in to the Lisp program. I didn't know how to do that linking, but I reasoned that writing an interpreter for this trivial language (all it had was set variable, fetch variable, and string concatenate) was easy, so I wrote an interpreter in C. So, ironically, Tony wrote a Lisp program (with one small routine in C) because he was a C programmer, and I wrote a C program because I was a Lisp programmer.
In the end, we both got our theses done (Tony, Peter).
To learn more about Scheme consult some of the fine books (by Friedman and Fellesein, Dybvig, Queinnec, Harvey and Wright or Sussman and Abelson), videos (by Abelson and Sussman), tutorials (by Dorai, PLT, or Neller), or the reference manual.
I also have another page describing a more advanced version of Lispy.