Lecture 20: Variable Assignment

Expressed and Denoted Values

In your textbook so far, you've seen a discussion of expressed and denoted values.

Expressed values: values that can be returned from expressions. By definition, eval-expression returns expressed values.

Denoted values: what are bound to variables in environments.

These sets of values, plus other parts that go into the way we store data for our language make up what is called a data model.

In the models we've used so far, the set of expressed values and the set of denoted values are the same. When we first built the interpreter, we had only numbers:

	Expressed Values = Number
	Denoted Values   = Expressed Values

When you added lists in a previous homework assignment, these became new expressed values:

	Expressed Values = Number + List
	Denoted Values   = Expressed Values

When we added functions, they too became new expressed values:

	Expressed Values = Number + List + Procval
	Denoted Values   = Expressed Values

Variable Assignment

Let's now add variable assignment to our language. (We'll come back to the data model idea in a moment.)

Syntax:

The BNF for variable assignment in ELL is

    <expression> = set <identifier> = <expression>

To add it, we add the following line to our grammatical specification:

    (expression ("set" identifier "=" expression) varassign-exp) 

Examples

Here's a simple assignment expression:

   set x = add1(x) 

We can sequence assignments using let expressions:

   let z = 20
   in let temp = set z = 19
      in z

This might seem strange, but let expressions are the only way we have to cause sequencing until we add an expression-sequencing construct (like begin) to our language. (You'll add this in HW-23.)

Here's how to read this let expression:

Let the variable "z" be 20 in evaluating the following expression:
   Let the variable "temp" be the result of setting "z" to 19 in the following expression:
       Evaluate z

When we evaluate z, even though it was initialized to be 20, it has been assigned (changed) to be 19.

Abstract Syntax

Here's the abstract syntax generated by SLLGEN for variable assignment:

    (varassign-exp 
        (id symbol?) 
        (rhs-exp expression?))

Behavior

Here's what we'd like to do for a variable assignment:

1. Evaluate the rhs-exp.
2. Find out where the identifier stores its value.
3. Put the result of the rhs-exp into where the identifier stores its value.

Changing Our Data Model

So, how do we "find out where the indentifier stores its value"? How do we even represent that? To do this, we need to change our data model.

	Expressed Values = Number + List + Procval
	Denoted Values   = Ref (Expressed Values)

The change is that variables are now bound conceptually to references to expressed value, not expressed values themselves.

Going back to the steps we identified earlier for the desired behavior, we can rewrite these steps in terms of the data model:

1. Evaluate the rhs-exp to get its expressed value.
2. Apply the environment to the identifier to get its denoted value.
3. Put the expressed value of the right hand side in the denoted value of the identifier.

Implementing References

Since our values are stored in Scheme vectors, we can build a reference type that points to a particular vector and contains an index into that vector.

(define-datatype reference reference?
  (a-ref
    (position integer?)
    (vec vector?)))

(define primitive-deref
  (lambda (ref)
    (cases reference ref
      (a-ref (pos vec) (vector-ref vec pos)))))

(define primitive-setref!
  (lambda (ref val)
    (cases reference ref
      (a-ref (pos vec) (vector-set! vec pos val)))))

(define deref 
  (lambda (ref)
    (primitive-deref ref)))

(define setref! 
  (lambda (ref val)
    (primitive-setref! ref val)))

Let's also add a new function apply-env-ref to our environment implementation that returns a reference to where the variable is stored. (Our current apply-env returns the expressed value--we want the denoted value.)

(define apply-env-ref
  (lambda (env sym)
    (cases environment env
      (empty-env-record ()
        (eopl:error 'apply-env-ref "No binding for ~s" sym))
      (extended-env-record (syms vals env)
        (let ((pos (rib-find-position sym syms)))
          (if (number? pos)
            (a-ref pos vals)
            (apply-env-ref env sym)))))))

Implementing Assignment

Now that we have the necessary machinery in place for references and getting references to stored variables, implementing assignment is easy:

(define eval-expression 
  (lambda (exp env)
    (cases expression exp
      (lit-exp (datum) datum)
      (var-exp (id) (apply-env env id))
      (varassign-exp (id rhs-exp)
        (begin
          (setref! 
            (apply-env-ref env id)
            (eval-expression rhs-exp env))
          1))
      ...
    )))

Notice that we call apply-env-ref to get a reference to the id, then we evaluate the right-hand side of the assignment (rhs-exp), then we use setref! to change the referenced location to contain the new expressed value.

Remember that this new assignment expression is an expression, not a statement, so it needs to return a value. What value? This implementation always returns "1" for the result of an assignment. We could change the implementation to return the expressed value assigned to the variable:

(define eval-expression 
  (lambda (exp env)
    (cases expression exp
      (lit-exp (datum) datum)
      (var-exp (id) (apply-env env id))
      (varassign-exp (id rhs-exp)
        (let ((val (eval-expression rhs-exp env)))
          (setref! 
            (apply-env-ref env id)
            val)
          val))
      ...
    )))

The complete interpreter for Lecture 20.

Last updated at 9:54 am on Friday, August 27, 2004.