On the semantics of programming languages
by Michał Grabowski
Complex constructions of a high level programming language are usually explained in terms of a translator (interpreting program) of the given language. For instance, the riddle
var a,b,c:integer; 
procedure p(varx1,x2,x3:integer; 



procedure f(par1:integer;var par2,par3:integer)); 

var loc:integer; 

procedure q(y1:integer;var y2,y3:integer); 


begin 



y1:=y3;y3:=y2;y2:=loc; 



f(y2,y3,y1) 


end; 

begin 


x1:=x1+1;loc:=x1; 


if x1<6 then p(x1,x2,x3,q) else f(x1,x2,x3); 

end; 
procedure r(z1:integer;var z2,z3:integer); 

begin 

end; 
begin 

a:=1;b:=2;c:=3; 

p(a,b,c,r); 

write (a,b,c); 
end 
is often explained in terms of activation record stacks, static links, procedure code addresses etc. You might ask then: "What's the good of having a highlevel language, if you have to get down to a much lower level in order to understand it well?" What's more, it quickly turned out that e.g. PASCAL in the version of one translator is not exactly the same PASCAL as yielded by another one. But then, what is PASCAL, in fact? For example, do declarations of variables have any contextindependent meaning, as "things in themselves", or is their meaning provided by the instructions that follow them?
By the end of the 1960s the creation of computer independent methods for defining the meaning of programming language constructions was considered a major intellectual challenge. The first satisfactory solution (denotational semantics) came from a group of mathematicians and computer scientists from the Oxford University in the 70s.
Is there a formal deduction system, that would allow to prove that a program computes some given function without making reference to any translator? Yes, such formal systems indeed exist. To prove their consistency is a very hard task that leads to very subtle semantics of programming languages and to considerations about object types. Even very abstract versions of problems that may appear are so complex, that they require tools derived from domain theory, the l
calculus, intuitionistic logic, category theory, game theory and computation complexity theory.
