Specification

Introduction

• An environment is a function whose domain is a finite set of variables, and whose range is the set of all Scheme values. Since we adopt the usual mathematical convention that a finite function is a finite set of ordered pairs, then we need to represent all sets of the form

  { (*var_1*,*val_*1), ..., (*var_n*,*val_n*) }

  where the var_i **are distinct variables and the val_i **are any Scheme values.

• We sometimes call the value of the variable var in an environment env its binding in env.

Environment Interface

Constructors

• (empty-env) ⇒ [] (empty environment)
• (extend-env var val [f]) ⇒ [g] (new environment with a new binding)

Observers

• (apply-env [f] var) ⇒ f(var) ⇒ val (bound value of var in environment f)

Grammar

Env-exp ::= (empty-env) Env-exp ::= (extend-env Identifier Scheme-value Env-exp)

Representation

The Interpreter Recipe

1. Look at a piece of data.
2. Decide what kind of data it represents.
3. Extract the components of the datum and do the right thing with them.

Data Structure (Tagged Data) Representation

In the most basic implementation, we represent environments as tagged data: (list tag ...)

;; empty-env : () -> Env
(define empty-env
	(lambda () (list 'empty-env)))

;; extend-env : Var x SchemeVal x Env -> Env
(define extend-env
	(lambda (var val env)
		(list 'extend-env var val env)))

;; apply-env : Env x Var -> SchemeVal
(define apply-env
	(lambda (env search-var)
		(cond ((eqv? (car env) 'empty-env)
					 (report-no-binding-found search-var)
					((eqv? (car env) 'extend-env)
					 (let ((saved-var (cadr env))
								 (saved-val (caddr env))
								 (saved-env (cadddr env)))
								(if (eqv? search-var saved-var)
										saved-val
										(apply-env saved-env search-var))))
					(else (report-invalid-env env)))))