Meeting 09 - Static Scoping

Bor-Yuh Evan Chang

Tuesday, September 24, 2024

\(\newcommand{\TirName}[1]{\text{#1}} \newcommand{\inferrule}[3][]{ \let\and\qquad \begin{array}{@{}l@{}} \TirName{#1} \\ \displaystyle \frac{#2}{#3} \end{array} } \newcommand{\infer}[3][]{\inferrule[#1]{#2}{#3}} \)

Meeting 09 - Static Scoping

What questions does your neighbor have?

In-Class Slides
In-Class Jupyter
Book Chapter

Announcements

• Lab 2 due this Friday (or Monday?) 6pm

Today

• Preview Lab 2
• Static Scoping
• Triage Your Questions
  • Using VSCode or the terminal to test your code (on coding.csel.io)?
  • Auto-testing with GitHub Actions?
  • HW2?

Questions?

• Review:
  • How does a recursive-descent parser work, roughly?

Questions?

Review: Variable Binding and Scope

What’s variable binding?

What’s variable scope?

Variable Binding

How do you bind a variable in Scala?

In JavaScript?

JavaScripty

Let’s extend our abstract syntax type Expr.

defined trait Expr

defined trait Expr
defined class N
defined class Plus
defined class Var
defined class ConstDecl

Ask: What’s the scope of a variable binding in this representation?

Free Variables

Let’s define a function to compute the free variables of a JavaScripty expression:

defined function freeVars

e_n: N = N(n = 2.0)
e_plusnn: Plus = Plus(e1 = N(n = 2.0), e2 = N(n = 2.0))
e_var: Var = Var(x = "four")
e_plusvarvar: Plus = Plus(e1 = Var(x = "four"), e2 = Var(x = "four"))
e_constdecl: ConstDecl = ConstDecl(
  x = "four",
  e1 = Plus(e1 = N(n = 2.0), e2 = N(n = 2.0)),
  e2 = Plus(e1 = Var(x = "four"), e2 = Var(x = "four"))
)

defined function freeVars

fv_n: Set[String] = Set()
fv_plusnn: Set[String] = Set()
fv_var: Set[String] = Set("four")
fv_plusvarvar: Set[String] = Set("four")
fv_constdecl: Set[String] = Set()

Value Environments

What is the meaning of an expression with free variables?

: 
Compilation Failed

defined type Env
defined function eval

Start with just refactoring with the additional parameter.

: 
Compilation Failed

: 
Compilation Failed

defined function evalExpr

Renaming Bound Variables

const four = (2 + 2); (four + four)

const x = (2 + 2); (x + x)

const fuzz = (2 + 2); (fuzz + fuzz)

Discuss: We generally consider terms equivalent up to the renaming of bound variables (e.g., we “see” the three expressions given above as the “same” expression).

Let’s implement rename that renames all variables into "x0", "x1", etc.

defined function rename

defined function rename