Meeting 12 - Functions and Dynamic Scoping

Bor-Yuh Evan Chang

Thursday, October 3, 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 12 - Functions and Dynamic Scoping

What questions does your neighbor have?

In-Class Slides
In-Class Jupyter
Book Chapter

Announcements

• HW1 scores released
• Review with Peer on Unit 2 Thu-Fri Oct 3-4 to prepare for exam
• HW3 due Monday 6pm
• Exam on Units 1-2 next Tue Oct 8
  • 50 minutes in class
  • Accommodation letters confirmed (some weeks ago)?
    • Look out for note on Piazza about the extended-time location
    • During class time
• Accelerated section enrollment

Today

• Functions and Dynamic Scoping
• Triage Your Questions
  • HW3?
• Revisit Operational Semantics

Questions?

• Preview:
  • What is static versus dynamic scoping?
• Review:
  • What is the correspondence between judgment forms/inference rules/judgments and code?
  • What is a big-step operational semantics?

Questions?

Functions Are Values

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

\[ \begin{array}{rrrll} \text{values} & v& \mathrel{::=}& \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e_1 \\ \text{expressions} & e& \mathrel{::=}& e_1\texttt{(}e_2\texttt{)} \\ \text{variables} & x \end{array} \tag{1}\]

defined class Fun
defined class Call

defined function isValue

defined type Env
defined class DynamicTypeError

empty: Env = Map()
defined function lookup
defined function extend

Dynamic Scoping

Rule

\[ \inferrule[EvalCall]{ ??? }{ E \vdash e_1\texttt{(}e_2\texttt{)} \Downarrow v' } \]

We first try to implement function call in the most straightforward way. What we will discover is that we have made a historical mistake and have ended up with a form of dynamic scoping.

We extend the definition of the evaluation judgment form for function call \(e_1\texttt{(}e_2\texttt{)}\) with the \(\TirName{EvalCall}\) rule in the most direct way.

\(\fbox{$E \vdash e \Downarrow v$}\)

\(\inferrule[EvalCall]{ E \vdash e_1 \Downarrow \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e' \and E \vdash e_2 \Downarrow v_2 \and E[\mathop{}x \mapsto v_2] \vdash e' \Downarrow v' }{ E \vdash e_1\texttt{(}e_2\texttt{)} \Downarrow v' }\)

Implementation

defined function eval

defined function eval

Dynamic Type Error

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd2$Helper.isValue(cmd2.sc:1)
  ammonite.$sess.cmd6$Helper.eval(cmd6.sc:3)
  ammonite.$sess.cmd7$Helper.<init>(cmd7.sc:1)
  ammonite.$sess.cmd7$.<clinit>(cmd7.sc:7)

Instrumented Implementation

defined function eval
defined function eval

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd2$Helper.isValue(cmd2.sc:1)
  ammonite.$sess.cmd8$Helper.eval(cmd8.sc:5)
  ammonite.$sess.cmd8$Helper.eval(cmd8.sc:39)
  ammonite.$sess.cmd9$Helper.<init>(cmd9.sc:1)
  ammonite.$sess.cmd9$.<clinit>(cmd9.sc:7)

Test Case

???

const x = 1;
const g = (y) => x;
((x) => g(2))(3)

Dynamic Scoping

e_dynamicScoping: ConstDecl = ConstDecl(
  x = "x",
  e1 = N(n = 1.0),
  e2 = ConstDecl(
    x = "g",
    e1 = Fun(x = "y", e1 = Var(x = "x")),
    e2 = Call(
      e1 = Fun(x = "x", e1 = Call(e1 = Var(x = "g"), e2 = N(n = 2.0))),
      e2 = N(n = 3.0)
    )
  )
)

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd2$Helper.isValue(cmd2.sc:1)
  ammonite.$sess.cmd8$Helper.eval(cmd8.sc:5)
  ammonite.$sess.cmd8$Helper.eval(cmd8.sc:39)
  ammonite.$sess.cmd11$Helper.<init>(cmd11.sc:1)
  ammonite.$sess.cmd11$.<clinit>(cmd11.sc:7)

Fixing Dynamic Scoping

Closures

expressions e ::= 
values      v ::=
variables   x

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd12$Helper.<init>(cmd12.sc:1)
  ammonite.$sess.cmd12$.<clinit>(cmd12.sc:7)

• The example that exhibits dynamic scoping suggests some possible fixes to implement static scoping.
• We observe that a free variable use in a function body references a variable binding at the time the function is defined, not when the function body is evaluated.
• This suggests that a function body should be evaluated in the value environment when it is defined.

\[ \begin{array}{rrrll} \text{expressions} & e& \mathrel{::=}& \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e_1 \mid e_1\texttt{(}e_2\texttt{)} \\ \text{values} & v& \mathrel{::=}& \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e_1[E] \\ \text{variables} & x \end{array} \]

defined class Closure
defined function isValue
defined type Env
empty: Env = Map()
defined function lookup
defined function extend

Rules

\[ \inferrule[EvalFun]{ ??? }{ E \vdash \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e \Downarrow \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e [ E ] } \]

\[ \inferrule[EvalCall]{ ??? }{ E \vdash e_1\texttt{(}e_2\texttt{)} \Downarrow v' } \]

\(\fbox{$E \vdash e \Downarrow v$}\)

\(\inferrule[EvalFun]{ }{ E \vdash \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e \Downarrow \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e [ E] { } }\)

\(\inferrule[EvalCall]{ E \vdash e_1 \Downarrow \texttt{(}x\texttt{)} \mathrel{\texttt{=}\!\texttt{>}} e'[E'] \and E \vdash e_2 \Downarrow v_2 \and E'[\mathop{}x \mapsto v_2] \vdash e' \Downarrow v' }{ E \vdash e_1\texttt{(}e_2\texttt{)} \Downarrow v' }\)

Implementation

scala.NotImplementedError: an implementation is missing
  scala.Predef$.$qmark$qmark$qmark(Predef.scala:345)
  ammonite.$sess.cmd14$Helper.<init>(cmd14.sc:1)
  ammonite.$sess.cmd14$.<clinit>(cmd14.sc:7)

defined function eval
v_dynamicScopingFixed: Expr = N(n = 1.0)