Meeting 03 - Binding and Scope

Bor-Yuh Evan Chang

Tuesday, September 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 03 - Binding and Scope

In-Class Slides
Book Chapter

Reminders

• Laptop-use section: back row
• Use Piazza for all course communication.
  • Energetically engage in discussions with your classmates to help each other on the learning activities — for your Class Participation score.
  • For course administrative things (e.g., grade issues, GitHub access issues), use private messages on Piazza to “Instructors”.
• Follow the reading Schedule on the course website.

Reminders

• Recitation sections are lab sections — bring your laptop!
  • Last Week: Getting your development environment set up!
  • This Week: Finishing HW1

Announcements

• HW1 due Friday 6pm (with the 24-hour grace period for when “stuff happens”)

Today

• Triage Your Questions
• Preview HW1
• Finish 3.2 Basic Values, Types, and Expressions: A Scala crash course.
• Chapter 4 Binding and Scope: A Scala crash course.

Your Questions?

• Review:
  • What is the functional computational model? It was the computational model you learned first, right?
  • What is referential transparency?

Your Questions?

Value Bindings

res0_0: Int = 7
res0_1: Int = 10

In order to reuse results, we can introduce bindings

two: Int = 2
four: Int = 4
res2_2: Int = 7
res2_3: Int = 10

Declare a variable name bound to a value of an expression. What this means is carry out the evaluation steps for the expression until we get a value. Then bind the name to the resultant value.

Value Environments

How do we evaluate an expression with variable uses?

: 
Compilation Failed

Value Environments

We need a way of capturing what the variable names in scope are bound to — a value environment.

A value environment maps variable names to values:

\[ [x \mapsto v, \ldots] \]

Conceptually, evaluating a sequence of val declarations yields a value environment.

Value Environments

two: Int = 2
four: Int = 4
res5_2: Int = 7
res5_3: Int = 10

Substitution

How do we evaluate an expression with variable uses?

We “apply” the environment by substitution.

\[ [\ldots, \mathtt{four} \mapsto 4](\mathtt{four} + 3) \]

\[ = [\ldots, \mathtt{four} \mapsto 4](\mathtt{four}) + [\ldots, \mathtt{four} \mapsto 4](3) \]

\[ = 4 + 3 \]

\[ \longrightarrow 4 \]

Value Environments: Take-Home Points

• We know how to introduce bindings from variable names to values in Scala (i.e., val)
• A value environment is a map from variable names to values that stores the bindings.
• In order to evaluate an expression containing variable uses, we “apply” a value environment using substitution.
• Conceptually, evaluating a sequence of val declarations yields a value environment.

Scoping

: 
Compilation Failed

Shadowing

How do we read this?

a: Int = 1
b: Int = 2
c: Int = 6

Shadowing

Let’s pair up and find the binding positions for every variable use in the program below. What is the final environment? Can you rename variable bindings and uses consistently to eliminate the shadowing?

a: Int = 2
c: Int = 54
d: Int = 324

Shadow-Respecting Substitution

What if we “naively” applied substitution of env1: \([\mathtt{a} \mapsto 2]\) to the rest of the expression?

a: Int = 2
c: Int = 54
d: Int = 324

Free versus Bound Variables

: 
Compilation Failed

In any given expression \(e\), a bound variable is one whose binding location is in \(e\), while a free variable is one whose binding location is not in \(e\).

Free versus Bound Variables

A closed expression is one that has no free variables:

res10: Int = 7

An open expression is one that has at least one free variable (and thus cannot be evaluated with an empty environment).

Functions

defined function square
res12_1: Int = 16

Formal parameters must have type annotations, but return type can be occasionally inferred. Good practice is to declare the return type.

square: Int => Int = ammonite.$sess.cmd13$Helper$$Lambda$1959/0x0000000800ab6840@47447eb9
res13_1: Int = 16

square: Int => Int = ammonite.$sess.cmd14$Helper$$Lambda$1970/0x0000000800ac5040@e20639
res14_1: Int = 16

square: Int => Int = ammonite.$sess.cmd15$Helper$$Lambda$1976/0x0000000800ac8840@499591ef
res15_1: Int = 16

square: Int => Int = ammonite.$sess.cmd16$Helper$$Lambda$1982/0x0000000800acc040@1fa674b0
res16_1: Int = 16

defined function factorial
res17_1: Int = 24

Closures

An expression defining a function can refer to variables bound in an outer scope:

four: Int = 4
defined function plusFour
res19_2: Int = 8

Tuples

A tuple is a simple data structure that combines a fixed number of values:

oneT: (Int, Boolean) = (1, true)

Using Tuples

defined function divRem
divRemSevenThree: (Int, Int) = (2, 1)
div: Int = 2
rem: Int = 1

div: Int = 2
rem: Int = 1

div: Int = 2