CSc 520 - Principles of Programming Languages
40 : Scheme -- Metacircular Interpretation

Christian Collberg

Department of Computer Science

University of Arizona

1 Introduction

• In this lecture I'm going to show how you can define Scheme by writing a metacircular interpreter for the language, i.e. an interpreter for Scheme written in Scheme.
• Before we can do that, we first need to learn a few more this about the language

2 Let Expressions

• A let-expression binds names to values:
  1#1
  
• The first argument to let is a list of (name value) pairs. The second argument is the expression to evaluate.

2#2

3 Let Expressions...

• Let-expressions can be nested:

3#3

4 Imperative Features

• Scheme is an impure functional language.
• I.e., Scheme has imperative features.
• I.e., in Scheme it is possible to program with side-effects.

(set! var value)

Change the value of var to value.

(set-car! var value)

Change the car-field of the cons-cell var to value.

(set-cdr! var value)

Change the cdr-field of the cons-cell var to value.

5 Imperative Features...

• Example:

4#4

6 Dotted Pairs

• S-expressions are constructed using dotted pairs.
• It is implemented as a struct (called a cons-cell) consisting of two fields (the size of a machine word) called car and cdr.
• We can manipulate these fields directly:

5#5

7 Dotted Pairs...

• When the second part of a dottend pair (the cdr-field) is a list, and the innermost cdr-field is the empty list, we get a ``normal'' Scheme list:

6#6

8 Dotted Pairs...

• We can use set-car! and set-cdr! to manipulate the fields of a cons-cell directly:

7#7

9 Dotted Pairs...

• (cons A B) can be thought of as first creating a cons-cell on the heap (using malloc, for example), and then setting the car and cdr fields to A and B, respectively:

8#8

10 Loops

Scheme's ``for-loop'' do takes these arguments:

1. A list of triples (var init update) which declares a variable var, with an initial value init, and which gets updated using the expression update, on each iteration;
2. A pair (termination_cond return_value) which gives the termination condition and return value of the loop; and
3. a loop body:

9#9

11 Loops...

• Sum the numbers 1 to 4, printing out intermediate results:

10#10

12 Association Lists

• Association lists are simply lists of key-value pairs that can be searched sequentially:
  11#11
  
• The list is searchedy the list from beginning to end, returning the first pair with a matching key:

  (assoc key alist)

  Search for key; compare using equal?.

  (assq key alist)

  Search for key; compare using eq?.

  (assv key alist)

  Search for key; compare using eqv?.

13 Association Lists...

12#12

14 Association Lists...

• We can actually have more than one value:
  13#13
  

15 Apply

• Apply returns the result of applying its first argument to its second argument.

14#14

16 Eval

• (eval arg) evaluates its argument.

15#15

17 Eval...

• eval and quote are each other's inverses:

16#16

18 Programs as Data

• Scheme is homoiconic, self-representing, i.e. programs and data are both represented the same (as S-expressions).
• This allows us to write programs that generate programs - useful in AI, for example.

17#17

19 Evaluation Order

• So far, we have said that to evaluate an expression (op arg1 arg2 arg3) we first evaluate the arguments, then apply the operator op to the resulting values.
• This is known as applicative-order evaluation.
• Example:

18#18

20 Evaluation Order...

• This is not the only possible order of evaluation
• In normal-order evaluation parameters to a function are always passed unevaluated.
• This sometimes leads to extra work:

19#19

21 Evaluation Order...

• Applicative-order can sometimes also lead to more work than normal-order:

20#20

• Here, applicative-order evaluates all the arguments, although only one value will ever be needed.

22 Evaluation Order...

• Ordinary Scheme functions (such as +, car, etc) use applicative-order evaluation.
• Some special forms (cond, if, etc) must use normal order since they need to consume their arguments unevaluated:

21#21

23 A Metacircular Interpreter

• One way to define the semantics of a language (the effects that programs written in the language will have), is to write a metacircular interpreter.
• I.e, we define the language by writing an interpreter for it, in the language itself.
• A metacircular interpreter for Scheme consists of two mutually recursive functions, mEval and mApply:

22#22

24 A Metacircular Interpreter...

• We want to be able to call our interpreter like this:

23#23

25 A Metacircular Interpreter...

24#24

26 A Metacircular Interpreter...

• mEval handles primitive special forms (lambda, if, const, define, quote, etc), itself.
• Note that, for these forms, we must use normal-order evaluation.
• For other expressions, mEval evaluates all arguments and calls mApply to perform the required operation:

27 A Metacircular Interpreter...

25#25

28 A Metacircular Interpreter...

• mApply checks if the operation is one of the builtin primitive ones, and if so performs the required operation:

26#26

29 A Metacircular Interpreter...

• Some auxiliary functions:

27#27

30 A Metacircular Interpreter...

• Note that this little interpreter lacks many of Scheme's functions.
• We don't have symbols, lambda, define.
• We can't define or invoke user-defined functions.
• There are no way to define or lookup variables, local or global. To do that, mEval and mApply pass around environments (association lists) of variable/value pairs.

31 Readings and References

• Read Scott, pp. 592-606, 609-610