Interpreters

Tips for navigating the slides:

Press O or Escape for overview mode.
Press the copy icon on the upper right of code blocks to copy the code

Class outline:

Scheme: Programs as data
Interpreting Scheme
Special forms
Logical forms
Quotation
Lambda expressions
Define expressions

Programs as data

A Scheme Expression is a Scheme List

Scheme programs consist of expressions, which can be:

Primitive expressions: 2 3.3 #t + quotient
Combinations: (quotient 10 2) (not #t)

The built-in Scheme list data structure can represent combinations:


                    (list 'quotient 10 2)        ; (quotient 10 2)


                    (eval (list 'quotient 10 2))  ; 5

In such a language, it is straightforward to write a program that writes a program.

Quasiquotation

There are two ways to quote an expression:

Quote: '(a b) => (a b)
Quasiquote: `(a b) => (a b)

They are different because parts of a quasiquoted expression can be unquoted with ,


                    (define b 4)

Quote: '(a ,(+ b 1)) => (a (unquote (+ b 1))
Quasiquote: `(a ,(+ b 1)) => (a 5)

Generating code

Quasiquotation is particularly convenient for generating Scheme expressions:


                    (define (make-adder n) `(lambda (d) (+ d ,n)))
                    (make-adder 2)        ; (lambda (d) (+ d 2))

Interpreting Scheme

The Structure of an Interpreter

Eval

Base cases:

Primitive values (numbers)
Look up values bound to symbols

Recursive calls:

Eval(operator, operands) of call expressions
Apply(procedure, arguments)
Eval(sub-expressions) of special forms

⤹⤴

Apply

Base cases:

Built-in primitive procedures

Recursive calls:

Eval(body) of user-defined procedures

Special forms

Scheme evaluation

The scheme_eval function chooses behavior based on expression form:

Symbols are looked up in the current environment
Self-evaluating expressions (booleans, numbers, nil) are returned as values
All other legal expressions are represented as Scheme lists, called combinations
(<operator> <operand 0> ... <operand k>)

Evaluating combinations

The special forms can all be identified by the first element:


                    (if <predicate> <consequent> <alternative>)
                    (lambda (<formal-parameters>) <body>)
                    (define <name> <expression>)

Any combination that is not a known special form must be a call expression.


                    (define (demo s)
                        (if (null? s)
                            '(3)
                            (cons (car s) (demo (cdr s)))))  ; Special!
                    (demo (list 1 2))                        ; Call expression!

Logical special forms

Logical forms are special forms that may only evaluate some sub-expressions.

If expression: (if <predicate> <consequent> <alternative>)
And and or: (and <e1> ... <en>), (or <e1> ... <en>)
Cond expression: (cond (<p1> <e1>) ... (<pn> <en>) (else <e>))

The value of an if expression is the value of a sub-expression:

Evaluate the predicate
Choose a sub-expression: <consequent> or <alternative>
Evaluate that sub-expression to get the value of the whole expression

Quotation

'<expression> is shorthand for (quote <expression>)
'(1 2) is equivalent to (quote (1 2))

The scheme_read parser converts ' to a combination that starts with quote.

The quote special form evaluates to the quoted expression, which is not evaluated.

(quote (+ 1 2))
evaluates to the three-element Scheme list
(+ 1 2)

Symbols & Functions

Frames

A frame represents an environment by having a parent frame.

A frame is an instance of a Frame object, which has lookup and define methods.

In this interpreter, frames do not hold return values.

Global frame

y	3
z	5

f1: [parent=Global]

x	2
z	4

Define Expressions

Define binds a symbol to a value in the first frame of the current environment.
(define <name> <expression>)

Evaluate the <expression>
Bind <name> to its value in the current frame


                    (define x (+ 1 2))

Procedure definition is shorthand of define with a lambda expression.
(define (<name> <formal parameters>) <body>)
(define <name> (lambda (<formal parameters>) <body>))

Lambda Expressions

Lambda expressions evaluate to user-defined procedures


                    (lambda (<formal-parameters>) <body> ... )


                    class LambdaProcedure:
                        def __init__(self, formals, body, env):
                            self.formals = formals  # A scheme list of symbols
                            self.body = body        # A scheme list of expressions
                            self.env = env          # A Frame instance


                    (lambda (x y) (* x y))

Applying User-Defined Procedures

To apply a user-defined procedure, create a new frame in which formal parameters are bound to argument values, whose parent is the env attribute of the procedure.

Evaluate the body of the procedure in the environment that starts with this new frame.


                    (define (demo s)
                        (if (null? s)
                            '(3)
                            (cons (car s) (demo (cdr s)))))
                    (demo (list 1 2))