CS计算机代考程序代写 c/c++ compiler Java Lecture 4. Varlang

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

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

Related Posts