Lecture 6: Interp cont., Lexical vs. Dynamic Scope
---

:::warning
**Announcements**
- **Please sit in the first 2 rows of the room**.
- `A1: Values` graded, `A2: Functions` due tonight
- `A3: Interp` out:
- Last assignment before Quiz 1
- Preliminary deadlines: Sunday, Tuesday, Thursday, Sunday
- Quiz 1 in 2 weeks (Oct 9)
- Will share practice quiz next week
- Next help hours:
- Emily's 3-5pm tomorrow
:::

:::success
Agenda for today
- Interpreter logic continued:
- `hash` for value lookup, option type for result ([prior notes](https://hackmd.io/@avh/rkJE6XRiee#Using-a-hash-in-plait))
- Group exercise: semantics for divide
- Nuances of functions/lambdas as data
- Lexical vs. dynamic scope
:::

# `calc` Interp continued

We'll continue with our `calc` example from last class.

## Group exercise: semantics of `/`

Interpreters allow us to implement whatever semantics we want for operators, even if these semantics differ from the host/implementation language.

For example, dividing 1/0 in Racket and `plait` produces an error:

> (/ 1 0)
- Number
. . /: division by zero

But maybe we want our `CalcLang` to instead produce ∞. In Racket/plait, one version of ∞ is `+inf.0` (we can have positive and negative infinity, but for simplicity of this example, we'll just say _any_ division by 0 should result in `+inf.0`).

We can add `/` to our type definition as such:

(define-type MathExpr
  (e-num [value : Number])
  (e-const [name : Symbol])
  (e-add [left : MathExpr]
         [right : MathExpr])
  (e-div [left : MathExpr]
         [right : MathExpr]))

:::success
As a group, add a new case for `/` to `calc` such that division by 0 results in `+inf.0`. Be sure to maintain the left-to-right argument evaluation order.
:::

:::spoiler Think, then click!

Some groups first came up with something like the following implementation:

[(e-div x y)
   (if (zero? (calc y))
       +inf.0
       (/ (calc x) (calc y)))]

However, consider if `y` is a very large subterm: this implementation has to run the recursive procedure `calc`, including creating a deep recursive stack, **twice**! It also processes `y` before `x`, which does not respect the left-to-right evaluation order.

The following is the best solution, since it (1) avoids redundant recursion on `(calc y)` by using a let binding, and (2) it processes the arguments to division in left to right order, which matters here in producing the correct error if both `x` and `y` have errors.

[(e-div x y)
 (let ([x-result (calc x)]
       [y-result (calc y)])
   (if (zero? y-result)
       +inf.0
       (/ x-result y-result)))]

:::

#### A note on the result type of `calc`

In the `calc` example, we only have one value type, `Number`, so we used plait's built-in `Number` type for simplicity. On A3, there will be more than one value type (numbers, strings, booleans _and_ lambdas), so the stencil code uses a new datatype, `Value`, as the result type.

#### Full `calc.rkt` file

#lang plait

;; Define a data type, MathExpr, that can either be a
;; numeric value, an add/div of two arguments (left and
;; right), or a pre-defined mathematical constant.

;; This is our AST for our lecture language
(define-type MathExpr
  ;  Number is a type built in to plait
  (e-num [value : Number])
   ; Symbol is a type built in to plait
  (e-const [name : Symbol])
  ; Like our grammar, this type definition is recursive
  (e-add [left : MathExpr]
         [right : MathExpr])
  ; Divide case
  (e-div [left : MathExpr]
         [right : MathExpr])
  )

;; Note: this is similar to variables on A3 interp
;; Note that this hash is *immutable*: we aren't modifying
;; it: we're just making a new version with a value added
(define (create-consts)
  (let* ([init (hash '())]
         [justpi (hash-set init 'pi 3.14)])
    justpi))

(define consts (create-consts))

;; "calc" is our interpreter on these mathematical
;; expressions.                ; on A3:Interp, this is more
                               ; detailed, either num, or str,
                               ; lambda
(define (calc (e : MathExpr)) : Number
  (type-case MathExpr e
    [(e-num value) value]

    ; Give you some examples of using a hash, you'll
    ; need a hash in A3:Interp for variables
    [(e-const name)
      ; Lookup the name in our constant hash table
     (let ([res (hash-ref consts name)])
       (if (some? res)
           (some-v res)
           (error 'calc-error "const not found")))]
    ; (error 'calc-error "TODO, need to implement")]
    [(e-add left right)
     (+ (calc left) (calc right))]
    ; Choose to use different semantics!
    ; GROUP EXERCISE: for our calc lang, dividing by
    ; zero should NOT produce an error. Instead,
    ; any divide with 0 as the divisor should produce
    ; infinity (+inf.0). 
    ; Note: respect order of operation. 
    [(e-div x y)
     (let ([x-result (calc x)]
           [y-result (calc y)])
       (if (zero? y-result)
           +inf.0
           (/ x-result y-result)))]))

# Lexical vs dynamic scope

For `A3: Interp`, in addition to basic arithmetic operations similar to what we have covered, you'll also need to implement *creation* and *application* (e.g., function calls) of `lambda`s!

Let's think through an example of a lambda creation and application in Racket:

(define x 1)
(define f
    (lambda (y) (+ x y))) ; which x is used here?
(define z
    (let ([x 2]
          [y 3])
      (f (+ x y))))

:::success
Which value of x is used in line 2 when the lambda is called on line 7?

Is it:
- `1`, based on the bindings on line 1 in scope at the definition of the lambda?
- OR `2`, based on the binding on line 5 in scope at the application/call of the lambda?
:::

Around half the class voted for each of these two responses! It turns out that these responses correspond to two distinct ways of handling scope: **lexical scope** corresponds to answer `1`, and **dynamic scope** corresponds to answer `2`. Real languages *can* use either strategy (or a combination of the two), but the vast majority of modern languages use **lexical scope**.

### Terminology: free vs. bound variables

:::info
A bit more terminology:
- A variable, `x`, is **free** in an expression, `e`, if `x` is used in `e` but not defined within `e`. That is, its definition comes from outside of `e` itself.
- A variable, `x`, is **bound** in an expression, `e`, if every use of `x` within `e` refers to a definition of `x` within `e`.
:::

For example, if I have the lambda:

(define (f y) (+ x y)) ; call this el

Only `y` is bound within `el` (because it is defined by the lambda argument). `x` is free in `el`: we must get its value from the enclosing scope. That is, we assume the definition of `x` comes from some surrounding scope.

Which bindings do *free variables* of a function refer to when the function is applied? Lexical vs. dynamic scope determines the answer.

### Answer 1: lexical scope

> Free variables of a function refer to bindings in the environment where the function is defined, regardless of where it is applied.

In short: with **lexical scope**, function/lambda environments are created and remembered at **definition**.

### Answer 2: dynamic scope

> Free variables of a function refer to bindings in the environment where the function is applied, regardless of where it is defined.

In short: with **dynamic scope**, function/lambda environments are created at **application** (or call site).

In Racket (and most other languages!) closures implement lexical scope. This means: when you go to implement lambdas, the language implementation needs to **save the environment** at definition, along with the argument names and the lambda bodies.

Closures allow functions to use any binding in the environment where the function is defined, regardless of where it is applied.

You may wonder: are lambdas and closures the same? They are closely related, but not quite the same. Lambdas refer to anonymous (unnamed) functions. Closures are lambdas that are closed over their environment (that is, that have lexical scope). For example, original LISP implemented lambdas, but used dynamic scope, and thus did not have "closures" by today's terminology.

# Lexical scope in the world

Racket, and almost every other language you might encounter, use **lexical scope** by default.

Historically, the original version of LISP used dynamic scope. Some modern languages incorporate aspects of dynamic scope: for example, the statistical language R allows a form of dynamic scope via its ["super assignment" operator `<<-`](https://prl.khoury.northeastern.edu/blog/2019/09/10/scoping-in-r/).

# How are lambdas implemented?

Now that we know that most languages use ==lexical scope==, how does that inform how we *implement* lambda values (as data!) within an interpreter?

:::success
Think-pair-share: what data does an interpreter need to store when it encounters a `lambda` value definition?

For example, if we have the following:

(define x 1)
(define (f y) (+ x y))

We know the interpreter needs to add `{x -> 1}` to the environment after line 1. In terms of implementation code in `plait`, the `x` would be a `Symbol`, the `1` could be just a `Number` or a type wrapping a `Number` as a `Value`, and the environment itself could be a hash.

But what about after line 2? How does the `lambda` get stored as `{f -> ????}`? That is, what data does the interpreter need to "remember" upon a lambda/function definition?
:::

:::spoiler Think, then click!

Different pairs came up with different answers, but the core ideas are that we need to remember the *body* of the lambda as data (e.g., that we are adding `x` and `y` with `'(+ x y)`), the number and names of the arguments (e.g., a list of args `'(y)`), and the *environment that remembers the free variables, under lexical scope* (e.g., `{x -> 1}`).

Put another way, when we encounter a lambda as a value, we'll save the following data:
1. The body.
2. The argument list.
3. The environment at definition.
:::

## Revisiting our function eval rule

With this information, we can revisit our function evaluation rule:

:::info
**Racket ==evaluation== rule: function call/application `(f e1 ... en)`**

- Check if `f` is a special form, for example `if`. If so, use the rule for that special form.
- Otherwise, ==evaluate== `f` to a function value `vf` with data `args =` `a1 ... an`, `body` = `<body>`, `env` = `<env>` (and otherwise report an error).
- ==evaluate== `e1` through `en` to values `v1, ..., vn`.
- ==evaluate== the body of the function `<body>` with the arguments bound to these values `{a1 -> v1, ..., an -> vn}` added to the environment `<env>` remembered by the `lambda` via lexical scope.
:::

# When does what happen when, again?

It's important to remember when things are evaluated!

In Racket (and most other languages you've used):

1. A **function body** is not evaluated until the function is called. A function body is evaluated every time the function is called. For example, the definition of `(define (f x) (/ 1 0))` does not result in an error, because the body is only evaluated on the function being _called_.

2. A function's **arguments** are evaluated before the called function's body. By convention, they are evaluated from left to right. For example, in `(g (+ 1 2) (* 3 4))`, the sum happens first, then the product, then the evaluation of `g`'s body with the two new bindings for the arguments.
3. A **binding** evaluates its expression when the binding is created, not every time the variable is used. For example, in `(let ([x (+ 1 2)]) (* x x))`, the sum happens just once, when `x` is bound to 3. Each use of `x` in the product just looks up `x` in the environment to get `3`.

As with lexical/dynamic scope, there are other options for "evaluation order" _not_ used by Racket. We'll talk about this more later in the semester when we get to _lazy_ evaluation!

---

:::warning
We didn't get here in Friday's class, and will continue this discussion on Monday.
:::

Most programming language designers now agree: _lexical scope is better_. Let's consider some reasons why.

## Why lexical scope?

### 1: Function meaning does not depend on name choices.

Consider this program:

; Snippet 1
(define (f y)
  (let ([x (+ y 1)])
    (lambda (z) (+ x y z))))

Now imagine we change the body of `f` to replace `x` with `q`, which we intend to be an equivalent program:

; Snippet 2
(define (f y)
  (let ([q (+ y 1)])
    (lambda (z) (+ q y z))))

Under **lexical scope**, this has no impact. The meaning of the lambda defined on line 3 does not change.

Under **dynamic scope**: depending on whether `x` or `q` are in the scope where the lambda defined on line 3 is _used_, we get different results! This is harder to reason about!

With *lexical scope*, we can understand the entire meaning of lambda just by examining its definition. There are no "hidden parameters" that are passed based on where the lambda later gets used.

### 2 Closures remember the data they need

Closures automatically “remember” the data they need.

For example, consider the function `greater-than-x` which produces a `lambda`:

; Snippet 3
(define (greater-than-x x)
  (lambda (y) (> y x)))

(define (no-negs xs)
  (filter (greater-than-x -1) xs))

(define (all-greater xs n)
  (filter (lambda (x) (> x n)) xs)

Under **lexical scope**, when `(greater-than-x -1)` is evaluated on line 5, the lambda is saved as a closure over the environment that binds `x` to `-1`, as intended. When `(lambda (y) (> y x))` is evaluated inside the body of `filter`, `x` will be mapped to `-1`.

Under **dynamic scope**, when `(greater-than-x -1)` is evaluated on line 5, the value of `-1` is **not saved**. When `(lambda (y) (> y x))` is evaluated inside the body of `filter`, one of two things will happen:
1. If there happens to be another `x` bound in that scope, that different value of `x` will be used!
2. Otherwise, we would get a `variable not found` error.

Neither case is what we intended! Thus, lexical scope is almost always a better choice for language design.

:::success
This is the end of the material covered by Quiz 1!
:::

---