Unbound variable in Racket-Scheme

Question

I am trying to implement a data structure to keep the state (variable bindings) of a program. I represent the state with association lists which are lists of key-value pairs.

An example association list is: '((x . 3) (y . (1 2)) (z . a)). In this example, key 'x has value 3, 'y has value '(1 2) and 'z has value 'a.

To manipulate the state, I have two functions:

1. (get-binding state var)

   This function returns the value symbol var is bound (assigned) to in state.

2. (set-binding state var val)

   This function returns a new state that is same as state with the exception that var is bound to val.

3. empty-state

   This variable corresponds to the state with no bindings. It is defined using define. Note: empty-state is not a function.

Example:

> (get-binding (set-binding (set-binding empty-state 'x 3) 'x 4) 'x)

which outputs 4.

Here is my code:

(define (enclosing-environment env) (mcdr env))

(define empty-state null)

(define (get-binding env var)
  (define (env-loop env)
    (define (scan vars vals)
      (cond [(null? vars)
             (env-loop (enclosing-environment env))]
            [(eq? var (mcar vars))
             (mcar vals)]
            [else
             (scan (mcdr vars)
                   (mcdr vals))]))
    (if (eq? env empty-state)
        (error "Unbound variable:" var)
        (let ([frame (first-frame env)])
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

(define (set-binding! env var val)
  (define (env-loop env)
    (define (scan vars vals)
      (cond [(null? vars)
             (env-loop (enclosing-environment env))]
            [(eq? var (mcar vars))
             (set-mcar! vals val)]
            [else
             (scan (mcdr vars)
                   (mcdr vals))]))
    (if (eq? env empty-state)
        (error "Unbound variable -- SET!:" var)
        (let ([frame (first-frame env)])
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

But it gives an error that says "Unbound variable -- SET!: x". How can I prevent it?

Answer 1

That is a lot of code...

What if an 'environment' is a function that looks up the value bound to a name? To get the value all we need do is apply the environment to the name:

(define (env-get env name)
  (env name))

And then to extend the environment, by creating another one, we look for the name but if we don't find it we defer to the base environment:

(define (env-set env name value)
  (lambda (nname)
     (if (eq? nname name)
         value
         (env nname))))

But, if the environment is empty, just error out.

(define env-empty
  (lambda (nname)
    (error "Unbound Variable: " nname)))

An example:

> (define env-1 (env-set env-empty 'x 4))
> (define env-2 (env-set env-1 'y '(a b)))
> (env-get env-2 'x)
4
> (env-get env-2 'y)
(a b)
> 

Answer 2

Do you realize that get-binding! and set-binding are the same function except for two lines? I suggest you combine them into one function:

(define (get/set-binding when-found when-unbound env var (val))
  (define (env-loop env)
    (define (scan vars vals)
      (cond [(null? vars)
             (env-loop (enclosing-environment env))]
            [(eq? var (mcar vars))
             (when-found val vals)]
            [else
             (scan (mcdr vars)
                   (mcdr vals))]))
    (if (eq? env empty-state)
        (when-unbound var)
        (let ([frame (first-frame env)])
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

Then you can fix the error. The problem stems from the fact that there's no way to modify null, so you can't introduce a binding by modifying an argument. You can only do it through the return value. You could define set-binding! like this:

 (define (set-binding! env var val)
     (set/get-binding (λ (val vals)
                         (set-mcar! vals val)
                         env)
                      (λ (var)
                         (add-binding var val env)) env var val))

To define add-binding, I have to make some guesses as to the structure of env based on your code. I'm going to assume that env is an mlist of frames, and that a frame is this:

(define-struct frame (variables values))

I'm going to further assume that if env has any frames, you want the new variable to be added to the first frame.

If those assumptions hold true, then add-binding would be defined like this:

(require compatibility/mlist)

(define (add-binding var val env)
  (if (null? env)
      (mlist (make-frame (mlist var) (mlist val)))
      (let ((first (mcar env)))
        (set-frame-variables! (mcons var (frame-variables first)))
        (set-frame-values! (mcons val (frame-values first)))
        env)))

Since this version of set-binding! returns a brand new env if you pass null for env, you need to always assign the return value of set-binding!:

Correct usage:

(set! env (set-binding! env var val))

Incorrect usage:

;; If env is null, the new binding is immediately garbage-collected.
(set-binding! env var val)

Answer 3

Premises

1. The error is defined in the code.

2. It is thrown when the value for env passed to set-binding! is eq? to null aliased as empty-state.

3. env is compared to null before (var . val) is added to env.

Conjecture

The initial environment is empty...i.e. null or aliased as empty-environment.

Solution

Don't treat an (eq? env empty-state) as an error condition...at least until after initialization.