Scoping Rules and Symbol Bindings

box

We will introduce many fundamental concepts (binding and scoping) and syntactic forms in this lecture.

Symbols, bindings and scopes

So far, we have shown how to specify different types of data (and sprinkle of functions), but like any programming languages, we need a way to assign them to symbols.

Symbol bindings

A binding is a mapping from a symbol to a value. We write a binding as:

$$ s \mapsto v $$

to denote that symbol $s$ is bound to the value $v$.

Scope

• Definition

  A scope $\sigma$ is a mapping of a group of symbols to values. The set of symbols that are mapped to some value is called the domain of the scope, $\mathrm{dom}(\sigma)$. A bound symbol is a symbol $s\in\mathrm{dom}(\sigma)$. Namely, $\sigma(s)$ is defined. Otherwise $s$ is free with respect to the scope $\sigma$.

• Expressions

  Every expression $e$ exists inside some scope $\sigma$. The symbols used in $e$ are resolved to values according to the scope $\sigma$.

• Nested Structures of Scopes

  Scopes are nested. Together, scopes form a tree structure where the root is the top-level scope.

• Scoping Rules

  There is a set of simple rules that determine the scope of expressions.

Scopes in Clojure

Let's look at how scopes are created in Clojure.

Top-level scope

• The top level scope exists by default. All other scopes are created by the Clojure program.

• Symbols in the top-level scope are created by def and defn.

  split=6

  (def pi 3.1415)
  (defn add [x y]
    (+ x y))
  

  • $\mathrm{dom}(\mathrm{toplevel}) = \{\mathtt{pi}, \mathtt{add}\}$
  • The bindings are:
    • $\mathrm{toplevel}(\mathtt{pi}) = 3.1415$
    • $\mathrm{toplevel}(\mathtt{add}) = \mathrm{function\ object}$

Let-form creates new child-scopes

• Inside any scope $\sigma$, one can use the (let ...) form to create a child-scope $\sigma'$.

• The child scope will have the additional bindings defined by in let form.

  split=6

  (let [x 1 y 2]
   (let [a "hello"
         b "world"
         x 100]
     ...))
  

  |
  |
  $\sigma: x\mapsto 1,\ y\mapsto 2$
  |
  |
  $\sigma_\mathtt{let}: a\mapsto \mathtt{"hello"},\ b\mapsto\mathtt{"world"},\ x\mapsto 100$
  |
  |
  ...
  

Function body is a new scope

• Function declaration creates a new scope for its body.

  (fn [x y]
    ...)
  

  $\sigma: \dots$
  |
  |
  $\sigma_\mathtt{fn} : x\mapsto ?,\ y\mapsto ?$
  |
  |
  ...
  

• Function invocation creates interesting complications in the scoping definition.

Scoping Rules

Closure

box

Definition

Let $\sigma_n < \sigma_{n-1} < \dots < \mathrm{toplevel}$ be a chain of nested scopes. The closure of $\sigma_n$, written $\overline{\sigma_n}$ is defined as a scope:

• $\mathrm{dom}(\overline{\sigma_n}) = \bigcup_{i=n}^\mathrm{toplevel} \mathrm{dom}(\sigma_i)$
• $\overline{\sigma_n}(x)$ is given by the most inner scope $\sigma_i$ such that $x\in\mathrm{dom}(\sigma_i)$

Resolution of symbols

• At any expression, symbols are resolved by the closure of the scope of the expression.

Function invocations are complicated

• Function declaration is defined in some scope $\sigma_\mathrm{def}$.

• Function invocations can occur at any other scopes $\sigma_\mathrm{invoke}$:

  split

  (def f (let [x 100] ; declaration scope
           (fn [y] (+ x y))))
  
  (let [x -100] ; invocation scope
    (f 42))
  

  |
  |
  $\sigma_\mathrm{def} : x\mapsto 100$
  |
  |
  $\sigma_\mathrm{fn} : y\mapsto ?$
  |
  |
  (+ x y)
  
  
  |
  |
  $\sigma_\mathrm{invoke} : x\mapsto -100$
  |
  |
  $\sigma_\mathrm{fn} : y\mapsto 42$
  |
  |
  (+ x y)
  

• Lexical scoping vs dynamic scoping are rules that determine which scope is the parent scope of the function body.

Lexical Scoping

box

During invocation, the scope of the body is determined by:

1. Parameters are bound to the arguments of the function.
2. The parent scope is the scope at the definition of the function.
3. Symbols are resolved using the closure of the chain of scopes.

This is the default behaviour, and is the recommended way to structure programs.

Example

(def f (let [x 100]
         (fn [y] (+ x y))))

(let [x -100]
  (println (f 42)))

; => 142

Dynamic Scoping

box

During invocation, the scope of the body is determined by:

1. Parameters are bound to the arguments of the function.
2. The parent scope is the scope at the invocation of the function.
3. Symbols are resolved using the closure of the chain of scopes.

This is considered dangerous because symbols in the function can be overriden by bindings at the site of invocation, making the code highly unpredictable.

Note: Clojure requires special form to switch to dynamic scoping rule.

Example

(def ^:dynamic x 0)
(defn f [y]
    (+ x y))


(binding [x -100] 
    (println (f 42)))

Summary