Where functional languages like FUN have definitions of variables, imperative languages have declarations. The basic idea is that the environment maps a variable to an address and there is a memory which maps addresses to values. The language IMP is a simple imperative language we can use to demonstrate declarations. IMP uses a hard-coded mapping from variable to memory location so this will need to be changed. We also extend IMP to include the construct
var x = e in p
This construct will lead to the allocation of a new memory address which will be initialised to the value of
An environment will be created which maps the variable
x to this address for the evaluation of the program
E be the environment which maps variables to addresses, and
M be a memory which maps addresses to
So, the variable
x will have the value
We will also need a function, New, which will allocate fresh addresses for a given memory.
The relational semantics for our extended IMP
uses the relations
E⊢e,M ⇒ c and
E⊢p,M ⇒ M',
as shown below.
From this we see that expressions,
e, do not have side-effects as they do not alter memory,
From the above we see that memory locations allocated with New are not deallocated. In the language above we could perform this deallocation in the declaration rule. For this to work we would need a function, Free, which would remove an address mapping from a memory. The declaration rule would then be:
R. Burstall. Language Semantics and Implementation. Course Notes. 1994.
Copyright © 2014 Barry Watson. All rights reserved.