Environments

An environment E associates a variable with a value, i.e. Environment=Var→Val. A common way to write an environment is as a set, e.g. if

1≤i≤n, xi∈Var∧vi∈Val
      

then the following is an environment:

{(x1,v1),(x2,v2),...,(xn,vn)}. 
	

Environments often need to be combined. If E1 and E2 are environments, and x is a variable, then the combination of the environments, E1E2, is defined as follows

E1E2(x) = E2(x) if defined, otherwise E1(x) if defined, otherwise undefined. 	
      

Here we see that E2 overrides E1.

Implementation

The following is a simple implementation of environments written in Barry's Prolog but it should work on most other Prolog systems.

%%%
%%% env_empty(?E)
%%%
%%% Succeeds if E is the empty environment.
%%%
env_empty([]).

%%%
%%% env_singleton(?Var, ?Val, +E)
%%% env_singleton(+Var, +Val, ?E)
%%%
%%% Succeeds if E is an environment with a single binding of Var-Val.
%%%
env_singleton(Var, Val, [Var-Val]).

%%%
%%% env_compose(+E1, +E2, -E)
%%%
%%% Succeeds and unifies E to the composition of E1 and E2. 
%%% The bindings of E2 override the bindings of E1 in E.
%%%
env_compose(E1, E2, E) :-
	append(E2, E1, E).

%%%
%%% env_lookup(+Var, +Env, -Val)
%%%
%%% Succeeds and unifies Val to the value associated with Var if Var-Val is a  binding
%%% in Env. Fails otherwise.
%%%
env_lookup(Var, Env, Val) :-
	member(Var-Val, Env).

      

References

R. Burstall. Language Semantics and Implementation. Course Notes. 1994.