Lecture 4. Varlang – variables
Lecture 4. Varlang – variables
February 1, 2021
Overview
I What is a variable?
I Varlang syntax
I Language design decisions related to variables: scoping
I Semantics of Varlang: how to evaluate a program with variables
What does variable mean in programming languages?
Abstraction: encapsulate the details
I Reuse
I Give a name to the complex definitions
I Easy to understand the code
I Make programming scalable
Some deeper thoughts on variables
In imperative programming languages:
I variable is a name associated with memory location
I you change state by assigning a new value to a variable in a
statement
In pure functional programming languages (no side effect at all, given the
same input, you get the same output):
I you change state by calling a function
I variables are similar to the math variables, they are symbols
I a function can be assigned to a variable
Varlang programs
(let ((x 1)) (+ x 1))
(let ((x 1) (y 2)) (* y x))
(let ((x 1) (y 2)) (let ((z 3)) (+ x y z)))
(let ((x 1)) (+ x (let ((y 1)) (+ x y))))
Varlang Syntax
Write Some More Varlang Programs
(+ (let ((x 1)) x) (let ((x 2)) x))
Scoping
I declaration, definition and use of a variable
I static and dynamic scoping
I free, bound variables
Definition and Use – Examples
Current VarLang Output:
$ (let ((x 5)) (let ((x 1) (y x)) (+ x y)))
6
$ (let ((x 5)) (let ((x 1)) (let ((y x)) (+ x y))))
2
Definition and Use – Examples
Scoping
I Keep variables in different parts of program distinct from one
another
I Match identifiers’ declaration with uses
I Visibility of an entity
I Binding between declaration and uses
I The scope of an identifier is the portion of a program in which that
identifier is accessible
I The same identifier may refer to different things in different parts of
the program: Different scopes for same name don’t overlap
I An identifier may have restricted scope
Lexical or Static Scoping – Varlang
I Effect of variable definition until the next variable definition with the
same name
I Scoping rule: variable definitions supersede previous definitions and
remain effective until the next variable definition with the same name
I This is a property of the program text and unrelated to the run time
call stack.
I Most of the programming languages: like C/C++/Java
I In static scoping, the compiler first searches in the current block,
then in the surrounding blocks successively and finally in the global
variables.
Static Scoping – VarLang Example
Static Scoping – VarLang Example
Static Scoping – VarLang Example
Static Scoping – VarLang Example
Static Scoping – VarLang Example
Static Scoping – VarLang Example
Static Scoping – VarLang Example
Static Scoping – VarLang Example
Static Scoping – VarLang Example
Static Scoping – VarLang Example
Static Scoping – VarLang Example
Static Scoping – VarLang Example
Dynamic Scoping
I Dynamic scoping the compiler first searches the current block and
then successively all the calling functions at runtime
I Dynamic scoping does not care how the code is written, but instead
how it executes.
I Each time a new function is executed, a new scope is pushed onto
the stack.
I Perl has both static and dynamic scoping, using different variables to
declare a variable: ”my” vs ”local”
Static vs Dynamic Scoping
I Static scoping is easy for programmers to reason about
I Dynamic scoping does not need to explicitly pass the parameters
through function calls
Free and Bound Variables
I free variable, a variable occurs free in an expression if it is not
defined by an enclosing let expression
I in program “x”, the variable x occurs free
I in program “(let ((x 1)) x)”, x is bound in enclosing let expression,
hence x is not free
I in program “(let ((x 1)) (+ x y))”, y is free
Varlang: Semantics and Their Implementations
An environment is a dictionary that maps variables to values at a
program point
Implementation of Varlang for Environment
Varlang: Use environment to evaluate Varlang program
The value of a variable is the first value from the left found in the
environment
Varlang: Semantics of a Program
I in an environment env, the value of a program is the value of its
component expression in the same environment env
Varlang: Implementation
Varlang: Semantics of Expressions
I Every expression has a value
I Expression passes the environment to their subexpressions
I There are expressions that do not change the environment and there
are expressions change the environment
Varlang: Semantics of expressions that do not change the
environment
I The addition expression neither defines new variable nor removes any
existing variable definitions. Therefore, an addition expression should
have no direct effects on the environment. (similar for the number,
subtraction, division, multiplication expressions)
I All of its subexpressions are evaluated in the same environment.
Varlang: Implementation
Revisit Varlang Syntax
Varlang: Semantics of expressions that change the
environment
Var Expressions:
I The meaning of a variable expression in a given environment is
dependent on the environment in which we are evaluating that
expression
I For example, the value of a var expression x in an environment that
maps name x to value 342 would be the numeric value 342. On the
other hand, in an environment that maps name x to value 441, the
value of the same var expression x would be the numeric value 441
Varlang: Semantics and Implementation – VarExp
Varlang: Semantics – LetExp
I Changes the environment: add new name-value pairs
I A let expression is also serving to combine two expressions exp and
exp’ into a larger expression
Varlang: Semantics of Expressions – LetExp Example
(let ((x 1) (y 1) (+ x y))
:
x : 1
y : 1
(+ x y) evaluates to 2
Varlang: Semantics – LetExp
I the value of a let expression is the value of its body exp’ obtained in
a newly constructed environment env’.
I It is obtained by extended the original environment of the let
expression exp with new bindings (variable name to value mapping).
Varlang: Semantics – LetExp
Note.
I Anything before the line denotes the condition(s), anything under the line denotes the result if the condition is true.
I There could be multiple conditions, these are usually separated by a space or, written in a new line before the straight line that
separates the condition.
Varlang: Implementation – LetExp
Review: VarLang
I What is a variable?
I VarLang Syntax: Write VarLang programs
I Decision for variables: Scoping
I definition/use of variables,
I free/bound variable
I VarLang semantics: Environment