State & Computational Effects

• So far, we have only considered the value produced by a computation. But a computation may have effects as well: it may read, print, or alter the state of memory or a file system. In the real world, we are always interested in effects: if a computation doesn’t display its answer, it doesn’t do us any good!
• What’s the difference between producing a value and producing an effect? An effect is global: it is seen by the entire computation. An effect affects the entire computation (pun intended).
• We will be concerned primarily with a single effect: assignment to a location in memory. How does assignment differ from binding? As we have seen, binding is local, but variable assignment is potentially global. It is about the sharing of values between otherwise unrelated portions of the computation. Two procedures can share information if they both know about the same location in memory. A single procedure can share information with a future invocation of itself by leaving the information in a known location.

Store

• We model memory as a finite map from locations to a set of values called the storable values. For historical reasons, we call this the store. The storable values in a language are typically, but not always, the same as the expressed values of the language. This choice is part of the design of a language.
• A data structure that represents a location is called a reference. A location is a place in memory where a value can be stored, and a reference is a data structure that refers to that place. The distinction between locations and references may be seen by analogy: a location is like a file and a reference is like a URL. The URL refers to the file, and the file contains some data. Similarly, a reference denotes a location, and the location contains some data.

Store-Passing Specifications

In store-based language, any expression may have an effect. To specify these effects, we need to describe what store should be used for each evaluation and how each evaluation can modify the store.

• In our specifications, we use σ to range over stores. We write [*l* = *v*]σ to mean a store just like σ, except that location *l* is mapped to *v*. When we refer to a particular value of σ, we sometimes call it the state of the store.

Effect-full

In a store-passing specification, the store is passed as an explicit argument to value-of and is returned as an explicit result from value-of. Thus we write (value-of exp1 ρ σ0) = (val1,σ1). This asserts that expression *exp*1, evaluated in environment ρ and with the store in state σ0, returns the value *val*1 and leaves the store in a possibly different state σ1.

Effect-free

Thus we can specify an effect-free operation like const-exp by writing (value-of (const-exp *n*) ρ σ) = (*n*,σ) showing that the store is unchanged by evaluation of this expression.

Implementation

We represent the state of the store as a Scheme value, but we do not explicitly pass and return it, as the specification suggests. Instead, we keep the state in a single global variable, to which all the procedures of the implementation have access.

;; the-store
(define the-store ’uninitialized)

;; empty-store : () → Sto 
(define empty-store (lambda () ’()))

;; get-store : () → Sto 
(define get-store (lambda () the-store))

;; initialize-store! : () → Unspecified
(define initialize-store! (lambda () (set! the-store (empty-store))))

;; reference? : SchemeVal → Bool 
(define reference? (lambda (v) (integer? v)))

;; newref : ExpVal → Ref 
(define newref 
	(lambda (val) 
		(let ((next-ref (length the-store)))
			(set! the-store (append the-store (list val))) next-ref)))

;; deref : Ref → ExpVal 
(define deref (lambda (ref) (list-ref the-store ref)))

;; setref! : Ref x ExpVal → Unspecified
(define setref!
  (lambda (ref val)
    (set! the-store
       (letrec ((setref-inner
									(lambda (store1 ref1)
			               (cond ((null? store1) (report-invalid-reference ref the-store)) 
													 ((zero? ref1) (cons val (cdr store1)))
					                 (else (cons (car store1) (setref-inner (cdr store1) (- ref1 1)))))))) 
					(setref-inner the-store ref)))))