Meeting 12 - Functions and Dynamic Scoping

Author

Bor-Yuh Evan Chang

Published

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}} $

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)