Lecture 4. Varlang – variables
February 1, 2021
Overview
What is a variable?
Varlang syntax
Language design decisions related to variables: scoping
Semantics of Varlang: how to evaluate a program with variables
What does variable mean in programming languages?
Abstraction: encapsulate the details
Reuse
Give a name to the complex definitions
Easy to understand the code Make programming scalable
Some deeper thoughts on variables
In imperative programming languages:
variable is a name associated with memory location
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):
you change state by calling a function
variables are similar to the math variables, they are symbols 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
declaration, definition and use of a variable static and dynamic scoping
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
Keep variables in different parts of program distinct from one another
Match identifiers’ declaration with uses
Visibility of an entity
Binding between declaration and uses
The scope of an identifier is the portion of a program in which that identifier is accessible
The same identifier may refer to different things in different parts of the program: Different scopes for same name don’t overlap
An identifier may have restricted scope
Lexical or Static Scoping – Varlang
Effect of variable definition until the next variable definition with the same name
Scoping rule: variable definitions supersede previous definitions and remain effective until the next variable definition with the same name
This is a property of the program text and unrelated to the run time call stack.
Most of the programming languages: like C/C++/Java
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
Dynamic scoping the compiler first searches the current block and then successively all the calling functions at runtime
Dynamic scoping does not care how the code is written, but instead how it executes.
Each time a new function is executed, a new scope is pushed onto the stack.
Perl has both static and dynamic scoping, using different variables to declare a variable: ”my” vs ”local”
Static vs Dynamic Scoping
Static scoping is easy for programmers to reason about
Dynamic scoping does not need to explicitly pass the parameters through function calls
Free and Bound Variables
free variable, a variable occurs free in an expression if it is not defined by an enclosing let expression
in program “x”, the variable x occurs free
in program “(let ((x 1)) x)”, x is bound in enclosing let expression,
hence x is not free
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
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
Every expression has a value
Expression passes the environment to their subexpressions
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
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)
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:
The meaning of a variable expression in a given environment is dependent on the environment in which we are evaluating that expression
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
Changes the environment: add new name-value pairs
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))
New Env: x:1 y:1
(+ x y) evaluates to 2
Varlang: Semantics – LetExp
the value of a let expression is the value of its body exp’ obtained in a newly constructed environment env’.
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.
Anything before the line denotes the condition(s), anything under the line denotes the result if the condition is true.
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
What is a variable?
VarLang Syntax: Write VarLang programs Decision for variables: Scoping
definition/use of variables, free/bound variable
VarLang semantics: Environment