▼Make your own meta-circular evaluator!
►4 Lookup in the environment
On this page:
4.1 Some tests
4.2 An environment
4.3 primitives
4.4 lookup
4.5 Environment as input to eval-exp
4.5.1 Looking up
4.5.2 eval-application
4.6 Done?
7.2
    ← prev  up  next → 

4 Lookup in the environment

If we’ve been through the previous part, we can keep using the same file. Or we can use 1-fixed-calculator.rkt as our starting point.

We see that most of the match-clauses in eval-exp look quite similar. We will do some steps of refactoring in order to not repeat ourselves, and also to be prepared for things to come. Later the users of the program will be able to define their own variables with names they choose themselves, so we do not want to continue to match on the names ('+, '- and so on) as we currently do in eval-exp. Instead we will look up the values of variables in some lookup-table that can be extended dynamically.

4.1 Some tests

You might want to copy them into the test module at the bottom of your Racket file. The tests are going to fail at first. By the end of this chapter they should pass.

(check-equal?
 (lookup (list (cons 'a 1)
               (cons 'b 2))
         'a)
 1)
(check-equal?
 (lookup (list (cons 'a 1)
               (cons 'b 2))
         'b)
 2)
(check-equal?
 (lookup (list (cons 'a 0)
               (cons 'a 1)
               (cons 'b 2))
         'a)
 0)
(check-exn
 exn:fail?
 (λ ()
   (lookup (list (cons 'a 1)
                 (cons 'b 2))
           'c)))

4.2 An environment

Idea is: Whenever we evaluate an expression, we will have an environment with bound variables and their values, and when we evaluate a variable reference, we will look up its value in the environment.

An environment can look like:

'((a . 5) (b . 4) (c . 3) (a . 7))

In this environment, looking up 'b should give us 4 and 'c should give us 3. 'a should give us 5. New bindings are added to the beginning of the list, and newer bindings shadow older ones. We can’t reach the 'a that is bound to 7.

4.3 primitives

We will start off by making a list called primitives containing our four primitive operators, and look up in this list every time the function eval-exp sees a symbol. We will use list to construct the list of bindings. Each binding will be a pair, constructed with cons.
(define primitives
  (list (cons '+ +)
        more bindings))

4.4 lookup

We will implement this as a recursive function. If the first binding in the list is equal to the symbol we are looking for then we return the corresponding value, otherwise we call lookup on what remains of the list. If the list is empty it doesn’t have the binding we’re looking for, and we will raise an exception.

We will make the lookup-function:
(define (lookup env s)
  (match env
    your code here))

It should have a couple of match-clauses:

One should match the empty list (e.g. (list) or '()), and throw an exception. We can use Racket’s error-function to raise an exception (see the function eval-exp for an example of use of error).
The more difficult part is to match a list with a binding (a cons-pair) as its first element. We can use a clause like:

[(list (cons name val) rest ...) your code here]

If this matches it will pick out the parts we need: name will be bound to a variable name and val to its value, and rest will be bound to the rest of the list. We then want to check if name is equal? to s, and return val if it is, or else call lookup on s and the rest of the list.

The tests we added should pass when we’re done.

4.5 Environment as input to eval-exp

We will pass primitives as an argument to eval-exp, and make eval-exp use it to look up values. So, in the definition of eval-exp, instead of

(eval-exp exp)

we will have have

(eval-exp env exp)

env will be the list of bindings we will use for looking up stuff.

We should modify the evaluate-function so that it passes primitives along to eval-exp.

4.5.1 Looking up

Now that eval-exp has an environment we can use it for when there are symbols:

[(? symbol?) your code here]

When this matches we want to apply our lookup-function to env and exp.

4.5.2 eval-application

Now, instead of having different match-clauses for '+ and '- and so on, we can have one clause for function application:

[(list fun args ...) (eval-application env fun args)]

We should be able to evaluate the fun-expression to get the correct function. We’re using a helper function:

(define (eval-application env fun args)
  your code here)

It should evaluate the fun-expression and all the expressions in the args list, and apply the evaluated fun to the evaluated args.

Should be pretty similar to what we used to do when we matched e.g. '+, only we don’t use a hardcoded function (like +), and we need to pass the environment along whenever we call eval-exp. It can be useful with a lambda function.

4.6 Done?

Run and see that all the tests pass.
Next is Definitions. We can keep using the Racket-file we’re working with, or skip to 2-lookup-in-environment.rkt.

    ← prev  up  next →