Specification

Overview

• In this design, we say that variables are mutable, meaning changeable.
• This design is called call-by-value, or implicit references. Most programming languages, including Scheme, use some variation on this design.

Values

A pair consists of two locations, each of which is independently assignable. The two locations in a pair are independently assignable, but they are not independently allocated. We know that they will be allocated together: if the left part of a pair is one location, then the right part is in the next location. So we can instead represent the pair by a reference to its left.

• ExpVal = Int + Bool + Proc + MutPair
• DenVal = Ref(ExpVal)
• MutPair = Ref(ExpVal) × Ref(ExpVal)

Implementation

; extending expressed values
(define-datatype expval expval?
	...
	(mutpair-val (pair mutpair?)
	...)

; new data type for mutable pairs
(define-datatype mutpair mutpair?
	(a-pair
		(left-loc reference?)
		(right-loc reference?)))

;; make-pair : ExpVal × ExpVal → MutPair 
(define make-pair
  (lambda (val1 val2)
    (a-pair
      (newref val1)
      (newref val2))))

;; left : MutPair → ExpVal 
(define left
  (lambda (p)
    (cases mutpair p
      (a-pair (left-loc right-loc)
        (deref left-loc)))))

;; right : MutPair → ExpVal 
(define right
  (lambda (p)
    (cases mutpair p
      (a-pair (left-loc right-loc)
        (deref right-loc)))))

;; setleft : MutPair × ExpVal → Unspecified 
(define setleft
  (lambda (p val)
    (cases mutpair p
      (a-pair (left-loc right-loc)
        (setref! left-loc val)))))

;; setright : MutPair × ExpVal → Unspecified 
(define setright
  (lambda (p val)
    (cases mutpair p
      (a-pair (left-loc right-loc)
        (setref! right-loc val)))))

Expressions

When a variable appears in an expression, we first look up the identifier in the environment to find the location to which it is bound, and then we look up in the store to find the value at that location. Hence we have a “two-level” system for var-exp.

Grammar Specification

The contents of a location can be changed by a set expression. We use the syntax

Expression ::= pair (Expression, Expression)
					 ::= left (Expression)
				   ::= right (Expression)
					 ::= setleft (Expression, Expression)
					 ::= setright (Expression, Expression)

Implementation

(define value-of
	...
	(newpair-exp (exp1 exp2)
		(let ((val1 (value-of exp1 env))
					(val2 (value-of exp2 env))) 
			(mutpair-val (make-pair val1 val2))))

	(left-exp (exp1)
		(let ((val1 (value-of exp1 env)))
			(let ((p1 (expval->mutpair val1))) 
				(left p1))))

	(right-exp (exp1)
		(let ((val1 (value-of exp1 env)))
			(let ((p1 (expval->mutpair val1))) 
				(right p1))))

	(setleft-exp (exp1 exp2)
		(let ((val1 (value-of exp1 env))
					(val2 (value-of exp2 env))) 
			(let ((p (expval->mutpair val1)))
          (begin (setleft p val2)
                 (num-val 82)))))

	(setright-exp (exp1 exp2)
		(let ((val1 (value-of exp1 env))
					(val2 (value-of exp2 env))) 
			(let ((p (expval->mutpair val1)))
                (begin (setright p val2)
			                 (num-val 83)))))
	...)