Environments - Programming Languages, Computer Science & Engineering Video Lecture - Computer Science Engineering (CSE) | Best Video for Computer Science Engineering (CSE)

welcome to lecture 11 so we will talk
about environments today after briefly
recap chelating what we did in the last
two lectures so in the last lecture we
discussed the notion of bindings and I
said that in general we are talking
about we are talking about identifier
value bindings in the case of constants
identifier location bindings in the case
of variables and in the case of
updations normally assignments we are
talking about location value bindings so
I also said that you could pragmatically
speaking bindings are such that you
could decide to stretch out a binding
for example the actual you could
actually split up an identifier location
binding into an identifier relative
location binding and then a relative
location to absolute location binding
and do it in a sort of temporally
decentralized manner and also depending
on the time at which you do various
kinds of bindings you might either have
early bindings late bindings or
somewhere in between
now bindings by themselves are a
pragmatic matter in the sense that they
really depend upon the implementation
but there is a certain core of bindings
which is not pragmatic which is a
semantics matter and that is just the
fact that there is some something known
as a constant and that a constant
declaration is somehow different from a
variable declaration that is a semantics
matter okay so how you actually do the
bindings is in is
for example if you take a language like
Pascal and let's say type-checking in
Pascal there is absolutely no guarantee
I mean that is also the typing of a
variable or typing of an identifier is
also binding there is absolutely nothing
in Pascal in the definition of the
Pascal language which says that you
should do your type checking only at
compile time in fact there's nothing
about the language which really
specifies that you should actually only
design a compiler I mean you could you
might as well design an interpreter if
it suits your convenience however the
language has been designed in such a way
as to make a compile time checking sort
of easy for example the name equivalence
and so on and the fact that you have to
declare before use
they make compile time checking easy so
normally so most Pascal compilers would
try to do as much of the type checking
at compile time so that the overheads do
not run into execution time I mean
that's that's that's an execution and so
it's a pragmatic issue in the sense that
you want us you want to make executions
faster than they are faster than as fast
as possible whereas it's not the case
with languages like snowball Lisp and so
on and so forth which want to produce an
extreme of flexibility so they delay all
bindings right up to the end and they
think of them and it's all done
dynamically but it's still a pragmatic
matter there is absolutely no reason why
you can't do you can't do some bindings
earlier ok so what we will now like to
look at is a semantic specification of
certain kinds of bindings especially the
creation of environments they're the
processing of declarations and how they
affect the rest of the language so let's
briefly go through the previous lecture
so we had this defined an expression
language of this kind in which I had
explicitly forbidden
I had explicitly forbidden identifiers
so even the and so it was a it was a
pure expression language consisting of
just numbers right so this production I
was absent and the reason is that an
identifier has a meaning only if it has
been only if it has got some binding so
we so what it means is that we can talk
about the meaning of an expression
containing identifiers only after we
have obtained a meaning of the
identifier in terms of some bindings in
in this case it's an identifier value
binding that we are looking at so that
the expression does not have a value the
meaning in in our case mostly represents
the ultimate value that an expression is
going to have and that expression does
not have a value to the identifier has a
value right so so we look at this but we
look at it in a slightly more holistic
fashion so let's also look at the
language of expressions so the
transition system so I assume that there
is a set of expressions capital script e
and a set of numerals script n which is
this so this script is the set of all
integer valued expressions e I use small
letters normally to denote that I am NOT
dealing with the syntax of the language
as considered by the non terminals in
the language so the capital letter is
here the capital easier denote non
terminal symbols of the grammar the
small e is here do not the syntax trees
that means your there's some processing
which is already occurred okay if you
want to look at it pragmatically so I'm
really looking at syntax trees rather
than the actual syntax of the expression
so which means there is no ambiguity so
I I will try to maintain this
distinction as far as possible
now and similarly n is the set of all
numerals in the underlying machine and
we defined a transition system with the
set of all configurations being the set
of all expressions the terminal
configurations being the set of numerals
which by the way are a subset of the set
of expressions yeah and and we defined
the three rules which actually which
actually give us a left to right
evaluation of expressions all right so
now in an expression language which
contains identifiers we will we will
take a simple language with declarations
very similar to what is obtained in ml
okay so right here so right now I'm not
too worried about types so I have
simplified the syntax a bit in an in
actual ml if this identifier is has got
a value then you would write let Val I
equals e in E and ok but since we are
not dealing with anything else except
values I have removed the keyword Val
okay so the language of expressions is
just consists of this and an expression
of this form right where of course there
is a declaration hidden inside inside
that expression okay and there's a
declaration means that there is a
binding occurrence of that identifier
and that declaration is itself expressed
in terms of an expression E and then if
you have a binding occurrence then you
have a scope for that binding occurrence
which is given by a complete expression
right so the identifier I might occur in
the final expression e as an applied
occurrence
so informally what are we saying if you
look at this expression what what we are
saying is that this expression is really
our ultimate goal the value of this
expression is what we want that is the
meaning that we want however this
expression is too complicated for
example and so we have used an
identifier inside that expression and
the meaning of that identifier is
somehow syntactically represented by
this by this declaration right so the
meaning of this entire expression is
really the meaning of e which contains
AI which which might contain possible
occurrences of this identifier I that
has been declared here the identifier I
of course has a value which is given by
another expression okay so you could
simplify these things but by for example
replacing all occurrences of this
identifier I by this expression P okay
and you would get a simple expression in
in the language however as you as you
must have seen through some of our ML
programs it's always a good idea to
allow for such declarations such namings
because very often they have they have a
meaning that is associated with a
problem domain and you would like to
separate out those things instead of
writing one long monolithic expression
you would like to split up the
expression into various parts there are
some more logically connected with the
solution of the problem okay so the
identifier is here in ml could actually
be variables and function names but for
the present we will just consider
variables and ml being a functional
programming language the notion of a
variable is really that of an identifier
value binding and the reason I am NOT
going directly into pl0 declarations is
because the
constant declarations in pl0 are very
much like the variables in ml yeah so
they they both share the same kind of
binding characteristic they say the same
semantic characteristic that a variable
in ml is just in an ml program is just a
value and so is a constant in a pill
zero program or in a Pascal program so
it's just a value okay so so we look at
this we look at this declaration we look
at the whole expression language and
what is an ml program an ml program or
an ml like program is really just one
expression so if you look at if you look
at your if you look at the ML programs
that we have looked at that we have
already seen you can you can think of
them as being you have you have a
collection of functions or values
declarations and then you have a
function and that's what is compiled
then you have an expression whose value
is evaluated in that with those
functions so you can think of any ml
program as consisting of a let with a
huge number of declarations and finally
an expression which has to be valid what
happens in the case of an ml session is
that the outermost let in an end are
considered implicit and it's hidden and
you don't have to explicitly write it
but you should think of any ml program
or any functional language the same
holds and scheme to in any functional
language you can think of the entire
program as being enclosed in a huge let
in end and since it's an interactive
since it's an interactive program what
you are what you what
you the outermost let in an end or
consider implicit and you just after
having compiled all the declarations you
just give an expression to give a to
find a value but each call to an
expression there is really like having
an entire program which is with all
those declarations enclosed in a let in
end yeah so so so what we are doing so
right now is actually fairly general so
let's look at the notion of identifier
and so as in any area of mathematics or
logic we have to define when identifiers
are free yeah the notion of binding
means that an identifier gets bound to
something okay otherwise it's free and
what is the meaning of free given a
certain given a certain expression or a
sentence of a language the free
identifiers are those which do not have
any declarations in that sentence that
sentence is supposed to be part of let's
say a larger sentence in which those
free identifiers will get a binding okay
so a free identifier is one given a
sentence a free identifier is one which
has only applied occurrences and no
binding occurrences right so we can
define the notion of freeness of
identifiers by looking at the structure
of this syntax tree and if and we can
define it by induction on the syntax
tree so if you had so let's look at our
grammar for expressions and we will
follow the we'll follow the syntax
we'll follow the syntax of this grammar
as closely as possible so you have this
set of expressions okay and the notion
of free identifiers is that given any
given any numeral corresponding to
corresponding to this production give
any given any sorry-sorry
given any numeral the set of free
identifiers in it is empty so if the set
of free identifiers isn't is a set of
it's a set of names that occur in it
with without a declaration so this in
any integer value for example the set of
free identity I'm sorry in if given any
identifier which is also an expression
it it is the singleton set of
identifiers given any expression of this
form with with this little Oh being a
the root operator of this syntax tree
the free identifier Xin this expression
is just the union of the free
identifiers Xin the individual
components and if you have a let
construct then the actual expression
value that you're interested in is e 2
and the free identifier of this entire
expression a let construct is a complete
expression the three identifiers of this
are just the set of all free identifiers
in e1 since you're using since you're
using probably some identifiers in e1 to
define this identifier I so it's a set
of all free identifiers in e1 and this I
will presumably be used in e2 which is
the whole purpose of having a
declaration of Phi however this any
occurrence of I here is an applied
occurrence which has a binding
occurrence here and so I is not in the
free occurrences of is not a free
identif
of this entire expression so this this
is by the way a set subset difference or
set subtraction if you like yeah so so
the set of free identifiers in this
entire expression is really the set of
all free identifiers in e1 e2 excluding
I okay similarly we could define the set
of bound identifiers and it follows a
similar pattern the set of bound
identifier is also is also defined by
induction on the structure of the syntax
tree so numerals and ident numerals and
simple identifiers a simple identifier
is by the way free yeah so so the
numerals and simple identifies do not
have any bound identifiers in them and
the set of bound identifiers Xin an
expression of this form is just the
union of the set of bound identifiers in
the in do individual components note
however that these two expressions could
have the same identifier bound in
different ways
I mean you could have an X inside a one
with a declaration for X you could have
an X inside a two with a declaration for
X and the two x's need not be the same
yeah
however let's let's look at that later
so and in this case the set of bound
identifiers is just the set of all bound
identifiers Xin e to Union the set of
all bound identifiers in e1 and of
course in e2 any occurrence of I would
not be considered bound and so that has
to be bound separately right and the set
of all identifiers of an expression is
just the set of all free and the set of
all bounded split identifiers in it yeah
so the notion of bound identifies has to
do with already possessing a meaning
which which means that the expression
can be readily evaluated yeah so the
notion of so so so it's important to
keep this for a for example if you were
to the notion of freeness and bound
identifiers is exists in all programming
languages okay either through implicit
bindings or explicit declarations so if
you look at a completely closed program
if you look at a complete Pascal program
there are no free identifiers except
those which come from the global
environment of the Pascal runtime system
okay so what are the identifiers that
come from the global environment of a
Pascal runtime system all those library
routines which are readily available so
if you look at just a complete Pascal
program supposing you don't use any of
the libraries library routines then the
complete Pascal program has absolutely
no free identifiers the program heading
has a name and that is itself a defining
or a binding occurrence of that name of
that identifier otherwise every every
other identifier if you're not using any
of the library routines every identifier
is declared before use so if you look at
the entire Pascal program there are
absolutely no free identifiers all
identifier czar bound so every that
means every identifier in that Pascal
program has a binding occurrence which
finds it completely right so a complete
program of this kind which has
absolutely no free identifiers is called
closed yeah so for any in any language
which has identifiers which allows
identifiers you can talk of a closed
sentence of their language as one which
has absolutely no free identifiers and a
ground sentence is one which has
absolutely no identifiers at all so in
fact the transition system we considered
for the expression language without any
identifiers consists of only ground
expressions right so closed and ground
these are two important terms which
occur in any formal language whatever
may be the formal language yeah so so so
the important thing is that a closed
sentence so if you look at a complete
Pascal program since there are no free
identifiers the the program itself can
be executed in an empty environment
because there are no identifiers which
required to be given a meaning from
outside a free identifier is one which
gets its meaning from outside the
sentence that you are currently looking
at so since so in a complete program
since all identifiers are bound they get
their meaning from within their sentence
and therefore a complete program
executes in an empty environment right a
ground sentence does not require an
environment at all since there are no
identifiers which require bindings
yeah so so what we have so our
expression our transition system for
expressions actually gives us a
transition system in an empty
environment so I have not actually
mentioned that so since we considered
only ground expressions without any
identifiers x' they obtain their meaning
in an empty n1 so it's so these these
things are very these things are
actually quite simple I mean after all
if you ask me well what is the value of
ax square plus BX plus C well clearly I
cannot give you that value unless you
can give me a meaning you can give me a
binding for ABC and X okay so under the
assumption so given that a has a value
something B has a value something else C
has a value something else in excess is
value something else then this
expression has a meaning in that
environment so that environment is just
the name value bindings for ABC and X
right so it's just a set of such
equality's name to value e qualities
yeah so we'll define the notion of an
environment for for our for this simple
ml like expression language given a set
V of identifiers at this at this moment
the only kinds of identifiers we are
interested in are identifiers which take
integer values yeah so they are like the
variables in ml an environment row over
the set V is just a mapping from capital
B to the set of numerals
so you can think of an environment as
actually a list or or more accurately a
set of values this should be a set of
variable value bindings and we can look
upon for any given collection of
variables V we can look at all the
environments that are possible so I'll
use env V to denote the set of all
environments over capital V very often
this subscript V the subscript V will be
omitted when it's either understood or
it's not important and so on and so
forth
yeah otherwise we are always considering
an environment in with a given set of
identifiers of course that set of
identifiers could be extendable right so
so let's look at let's look at the
Declaration language we could actually
extend its language a further so since
there is since declarations have a
semantics meaning completely different
they are logically a different entity
from expressions it's a good idea to
abstract that out as a separate
non-terminal which is something we have
already done and in fact by abstracting
it out as a separate non-terminal we
have also I mean the the language of for
example pl0 also gives them a separate
syntax and separate reserved words to
make it clear that is it this
it's semantically a different logical
entity from that of expressions are
commands so once you have this there is
absolutely no reason why you should have
only one
if I decorate there you could for
example have several identifiers declare
see so you have a separate declaration
language which whose basis is a single
declaration and whose and you can recur
on that basis and give sequences of
declarations which is what happens in
most programming languages right so now
what we have is our lie is that we have
a we have a programming language a
functional programming language whose
main non-terminal is the language of
expressions and there is an auxilary
language within it which is the language
of declarations and if you look at the
dependencies so for example the
expression language allows for
declarations inside expressions and
declarations in turn allow for
expressions inside declarations and they
both allow for identifiers right so so
so there is as you can see there is a
certain circularity in the entire
definition which is which is what
happens when you apply these things
inductively or recursively yeah so for
the moment will not talk about this but
it has some meaning that I'll explain
later so our language whatever we write
in green is really our language right so
let's let's look at some quick examples
for example so a typical sequential
binding could be of this form let pi
equals 3.14 1 semicolon 2 pi equals 2.0
star pi the semicolon is very important
in the sense that you're in a sequential
declaration what you are the sequencing
might be important what you're
explicitly is saying
is that the second declaration might
actually depend on definitions given by
the first declaration as in this case
very often of course this dependence is
not there in which case they could
actually be written in either order this
this is also typical in Pascal for
example you could have a constant
declaration of PI semicolon something
another constant which uses the previous
declaration of Pi in the evaluation of
its value so you could have a complete
expression in a constant declaration
provided all the identifiers in that
expression already have been declared
before right okay in in the case of
Pascal of course they should all be
constants - they can't be variables but
for the moment let's not worry about
that and the actual the actual
expression whose value you are
interested in is this where of course
this identifier radius is free in the
entire expression and presumably this
expression has been pulled out of some
context in which maybe radius has a
binding but this is this is an
expression in itself and we are not too
interested in context-sensitive
syntax so what we will assume
semantically is that this radius in
order for this expression to have a
value which is what we mean by the
meaning of an expression it is necessary
that there be there will be an
environment in which radius has a value
and once that is done I can have I can
evaluate this expression right so so you
can have sequential bindings like this
you could also have nested bindings like
this so the actual expression you are
interested in is let's say a star H
where H is free so the value of this a
star H is what you are interested in
and however you required you required
since the expression well presumably was
getting too complicated you had to
define this a and in order to define
this a I had to define this by okay
again here there are these two
identifiers two occurrences of the
identifier R which presumably was which
are free and so they they must so it's
not possible to evaluate this entire
expression unless R and H are given some
value from some external environment
unless they have been declared somewhere
in the controversy yeah so so you could
have nested bindings to okay and this is
in fact allowed in ml by by nested
bindings what you are doing is you are
really localizing this identifier a it's
local only to this scope between this
let in and end the identifier pi is
local to entirely this scope yeah all
right so since and such a construction
is possible because of the fact that an
expression can have a declaration in it
a declaration can have an expression in
it but if this expression is this is a
full-fledged expression there is
absolutely no reason why it cannot have
a declaration inside it right so so we
have to keep in mind the fact that such
things are possible when we evaluate
when we define the semantics of this
language
Yeah right so the localization of new
environments is something that will
define you so let's define an operation
on environments so assume you've got
some variable sets v1 and v2 whose union
is V note that I am NOT assuming that V
1 and V 2 are definite are necessarily
disjoint ok V 1 and V 2 could have some
common identifiers in them after all as
we saw in Bound expressions there's a
there was absolutely no reason why the
same identifier could not have been
bound in different bound differently in
different localities in different sub
sub expressions yeah so let's assume
that Rho 1 is an X is an environment
over V 1 this is a this is a short form
notation to indicate that Rho 1 is an
environment over V 1 Rho 2 is an
environment over V 2 then we'll define
this operation called Row 1 with Row 2
within brackets yeah we'll define this
as an operation I'm using light blue
always for Rose because for environments
because I have so far not actually
defined what an environment means in
concrete terms I have taken out the
minimum minimum information that I
require so as far as I'm concerned an
environment is not a data structure it's
an abstract entity which later after you
have semantically specified all that you
require of an environment you can come
out with a suitable data structure to
represent environments ok so the normal
coding conventions I will follow
throughout are that anything that's blue
is likely to
be somewhat abstract up in the sky
somewhere anything green is very
programming language oriented Brown is
something that's quite down-to-earth
maybe maybe related to the underlying
virtual machine black actually I have
black is something that I often use for
explaining things which is actually up
goes beyond the sky into outer space
which is very dark but it could also be
something very deep down inside the
earth you know so it some things could
be as black as coal so so I so I have a
sort of schizophrenic view towards black
but otherwise I'll use this car this
sort of color coding throughout yep so
I'll define a rho1 rho2 so that that is
a new environment it's so this is an
operation on environments which creates
a new environment for each identifier I
if I is in v2 then the binding given by
a row is the same as the binding given
by a row - okay for all identifiers that
occur only in v1 and not in V to the
binding given by row is the same as the
binding given by robot yes and we are
only considering we are only considering
as the set of identifiers in V 1 Union V
2 so there is no there's no other
possibility right so note that this is
an asymmetric operation and that row or
so we can call it as Rho 1 updated Rho 2
is not the same as Rho 2 updated robot
yeah
so we'll be requiring this operation as
you see right so so we'll define the
operational semantics of this since
since as I said if you look at our
grammar expressions require declarations
declarations also require expressions so
I so we cannot take we cannot isolate
the two completely so any semantics of
the expression language will depend upon
a semantics of the declaration language
and a declaration and any semantics of
the declaration language will depend
upon the semantics of the expression
language so we so if we have to give a
semantics now we have to give a holistic
semantics including both expressions and
declarations and we have to make it
complete right so let me quickly go
through this and I'll explain the finer
points next time yeah so so I'll start
with in exactly the form we have our
grammar the main language is the
language of expression so I'll start
with the transition system for
expressions now I have a difference I
have to consider only all those
expressions in the language over some
set of variables V of course very often
I'll just get rid of this Z so the set
of all configurations of expressions is
just the set of all expressions over V
and the set of our terminal
configurations is still the set of
values because the meaning of an
expression ultimately is just a value
right okay and we will define this
transition relation under the assumption
of an environment an expression which
contains identifies does not have a
meaning unless each of those identifiers
has a meaning in other words the
expression does not have a value unless
each of the identifiers has been given a
value so that value assignment to the
identifiers is going to be in this
Munroe yeah right so I will just I will
just quickly go through the modified
forms of these of the transition system
so the first thing of course is that we
have to introduce an axiom which says
that in any environment row give it that
bins are an environment is just a value
binding to each of the identifiers right
it's just a set of value bindings an
expression which is just an identifier
which is allowed by our grammar has a
value just given by the binding right so
given any identify and note I said once
before that our transition systems are
syntactic or symbol manipulations and
this symbol manipulation is that you
whenever you encounter the identifier I
this transition indicates that that is
really being replaced if you like by the
value given by the environment it's so
still symbol manipulation but symbol
manipulation in the abstract right so
the other two other three rules are
exactly as we had before except that now
we have to bring in the environment
because we really cannot this the rule
even does not really require an
environment however the e1 an
application of e1 could would often in
in the general case would never be
complete without an environment because
e one would be applied only after you
have successively applied III and e2
several times just go back to our basic
example of our transition system so what
would happen is we are specifying a left
to right method of evaluation so you
would be applying so given an expression
of the form e 1 some binary operation e2
you would keep applying a3 till the
left-hand operand
became a constant became a numeral then
you would start evaluating the
right-hand operand till that became a
constant and then you would just
evaluate this constant right so there
would be several applications of III
till the left hand operation became an
operand became a constant then several
applications of e2 till the right-hand
operand also became a constant and then
an application of e1 right so if you
look at this this this the the syntactic
application of these rules in a typical
large expression that's what would
happen so what in in the in in the in
the case of this and in the case of the
introduction of identifies what would
happen is before applying before an
expression like II 1 became a constant
there would have to be an application of
a call to an environment somewhere to
replace the ID ID the identifier is in
it by appropriate constants or literals
if you like right so there would be
interspersed in this process of
execution would be applications of inert
where identifiers are replaced by
constants okay and those and all of them
require this environment row right
so however so this is this is only for
the basic language of expressions which
does not contain any declarations so we
have to excuse we have to still give a
meaning for the let construct and the
let construct is something like this so
let's so let's look at this so the
meaning of a let construct of this form
is really the value of e however the
value of e depends upon this declaration
D inside the let construct and so there
is no way I can evaluate this expression
e till I have evaluated this declaration
D and evaluating the declaration D means
creating fresh bindings so which means
that this expression can make some
progress only if this processing of this
declaration can make some progress so if
this declaration moves from one from us
from D to some D Prime I am not yet
specified what it means for a
declaration to move from D to D prime
that is something since we are looking
at things in a top-down fashion it will
come later yeah
and supposing so several applications of
efore will finally reduce this
declaration to some environment Rho
prime okay and now I'm in a position to
evaluate this e and I can evaluate this
e and this e can move to some a prime
and how do I evaluate this e I evaluate
it really in the environment row updated
with Rho prime however this entire
expression the let construct really is
executed in the original environment row
with which it came which in the case of
a completely closed program this row
would be the empty set but in the case
of a program which is not completely
closed any expression need not be
completely closed
it would execute in some environment row
so once the declaration has been
completely evaluated to produce an
environment row Prime this expression
can be evaluated and the evaluation of
this expression proceeds in this
modified environment in this updated
environment row row Prime ok and now in
this modified environment essentially
what would happen is if there are no let
constructs within e the if there are no
nested bindings then you would be
applying rules he not a 1 e 2 and E 3 to
finally evaluate this expression by
several applications and having done
that what will happen is that you will
be left with a constant finally and the
result of this expression is just this
constant right but note that the entire
net construct really its environment is
only row and the abrasion row prime is
really a temporary change in a change in
the environment and that since it is
reversible right so there is a
reversible process so this temporary
change in the environment is necessary
in order to evaluate this expression but
really the environment in which the
entire let construct is being it is is
being executed is the original extreme
in the original environment that it
started out it yeah so so the
environments that the operations of
environments is a class II this is a
typical case of a reversible change in
the sense that if you apply these rules
systematically there is absolutely no
reason why you should be left with a
strange updated environment which is
different from what you started off
originally
you always end with the original
environment you started out with in a
completely closed plastic program you
start with an empty environment and
after you are executed you still have
nothing more than the empty environment
the completely closed Pascal program
executes in that NY in the original
global environment and as declarations
come new updations
which are temporary are created and as
those scopes are executed I exited those
updations go away automatically right
okay I'll stop here I'll continue again
on the declaration transition system
next time and we'll look at some
examples