3 A First Look at Interpretation
Now that we have a representation of programs, there are many ways in
which we might want to manipulate them. We might want to display a
program in an attractive way (“pretty-print”), convert into code in
some other format (“compilation”), ask whether it obeys certain
properties (“verification”), and so on. For now, we’re going to
focus on asking what value it corresponds to (“evaluation”—
Let’s write an evaluator, in the form of an interpreter, for our arithmetic language. We choose arithmetic first for three reasons: (a) you already know how it works, so we can focus on the mechanics of writing evaluators; (b) it’s contained in every language we will encounter later, so we can build upwards and outwards from it; and (c) it’s at once both small and big enough to illustrate many points we’d like to get across.
3.1 Representing Arithmetic
Let’s first agree on how we will represent arithmetic expressions.
Let’s say we want to support only two operations—
Why did we not include division? What impact does it have on the remarks above?
(define-type ArithC [numC (n : number)] [plusC (l : ArithC) (r : ArithC)] [multC (l : ArithC) (r : ArithC)])
3.2 Writing an Interpreter
Now let’s write an interpreter for this arithmetic language. First,
we should think about what its type is. It clearly consumes a
ArithC value. What does it produce? Well, an interpreter
evaluates—
Write your test cases for the interpreter.
Templates are explained in great detail in How to Design Programs.
(define (interp [a : ArithC]) : number (type-case ArithC a [numC (n) n] [plusC (l r) ...] [multC (l r) ...]))
(define (interp [a : ArithC]) : number (type-case ArithC a [numC (n) n] [plusC (l r) (+ l r)] [multC (l r) (* l r)]))
Do you spot the errors?
(define (interp [a : ArithC]) : number (type-case ArithC a [numC (n) n] [plusC (l r) ... (interp l) ... (interp r) ...] [multC (l r) ... (interp l) ... (interp r) ...]))
(define (interp [a : ArithC]) : number (type-case ArithC a [numC (n) n] [plusC (l r) (+ (interp l) (interp r))] [multC (l r) (* (interp l) (interp r))]))
Later on [REF], we’re going to wish we had returned a more complex datatype than just numbers. But for now, this will do.
Congratulations: you’ve written your first interpreter! I know, it’s
very nearly an anticlimax. But they’ll get harder—
3.3 Did You Notice?
I just slipped something by you:
What is the “meaning” of addition and multiplication in this new language?
First of all, there’s many different kinds of numbers: fixed-width (e.g., 32-bit) integers, signed fixed-width (e.g., 31-bits plus a sign-bit) integers, arbitrary precision integers; in some languages, rationals; various formats of fixed- and floating-point numbers; in some languages, complex numbers; and so on. After the numbers have been chosen, addition may support only some combinations of them.
In addition, some languages permit the addition of datatypes such as matrices.
Furthermore, many languages support “addition” of strings (we use scare-quotes because we don’t really mean the mathematical concept of addition, but rather the operation performed by an operator with the syntax +). In some languages this always means concatenation; in some others, it can result in numeric results (or numbers stored in strings).
This brings us to our first game of:
1 + 2
1 + 2
’1’ + ’2’
’1’ + ’2’
Now return to the question above. What semantics do we have? We’ve adopted whatever semantics Racket provides, because we map + to Racket’s +. In fact that’s not even quite true: Racket may, for all we know, also enable + to apply to strings, so we’ve chosen the restriction of Racket’s semantics to numbers (though in fact Racket’s + doesn’t tolerate strings).
If we wanted a different semantics, we’d have to implement it explicitly.
What all would you have to change so that the number had signed- 32-bit arithmetic?
In general, we have to be careful about too readily borrowing from the host language. We’ll return to this topic later [REF].
3.4 Growing the Language
We’ve picked a very restricted first language, so there are many ways we can grow it. Some, such as representing data structures and functions, will clearly force us to add new features to the interpreter itself (assuming we don’t want to use Gödel numbering). Others, such as adding more of arithmetic itself, can be done without disturbing the core language and hence its interpreter. We’ll examine this next (A First Taste of Desugaring).