:::warning
**Announcements**
- A0: Intro due 11:59pm tonight.
- Next help hours: (all L037)
- Emily 3-5pm Friday
- Alexa 6:30-8:30pm Monday
:::

:::info
**Agenda**

- `my-append` and the recursive call stack
- `cond` in favor of nested `if`
- Scope warmup
- Specifying semantics: evaluation rules
- Scope: local binding with `let` and `let*`
- Group exercise with `let` and `let*`
:::

# More Racket examples

## From last class group work: `my-append`

;; my-append : take two lists, produce the list that
;;             appends them
;; Input: two lists
;; Output: a single concatenated list
;; Tip: it may help to draw out the two lists as linked
;;     lists.

;; Example:
;; (my-append (list 1 2) (list 3 4))
;;   evaluates to value
;;   '(1 2 3 4)


(define (my-append l1 l2)
 (if (empty? l1)
      ; Base case: the first list is empty
      l2
      ; Otherwise, use a cons cell, recur on the rest
      ; of the first list
      (cons (first l1) (my-append (rest l1) l2))))

# Understanding the recursive call stack

How does `my-append` build up the right answer?

(define (my-append l1 l2)
 (if (empty? l1)
      ; Base case: the first list is empty
      l2
      ; Otherwise, use a cons cell, recur on the rest
      ; of the first list
      (cons (first l1) (my-append (rest l1) l2))))

Programs store data in two forms of memory: _the stack_, which tracks context for function calls, and _the heap_, which tracks dynamic data (such as `cons` cells). You saw _the stack_ in CS111 when you learned about *function call stack* and *stack traces* for errors.

The stack frame grows as functions are called, and shrinks when functions return.

If a function calls itself recursively, we get one stack frame per call (that is, frames are per call, not per function).

Here is one way to visualize the `my-append` called on lists `'(1 2) '(3)`

View of the function call stack
(grows downward)
---------------------------------
| my-append                      |
| l1 = '(1 2) ; first is 1       |
| l2 = '(3)                      |
| (first l1) = 1                 |
| context for recursive call:    |
| (cons 1 ...)                   |
| returns   '(1 2 3)             |
---------------------------------
| my-append                      |
| l1 = '(2) ; first is 2         |
| l2 = '(3)                      |
| (first l1) = 2                 |
| context for recursive call:    |
| (cons 2 ...)                   |
| returns  '(2 3)                |
---------------------------------
| my-append                      |
| l1 = '()                       |
| l2 = '(3)                      |
| base case: l1 is empty         |
| returns  '(3)                  |
---------------------------------

By `context for recursive call`, we mean that each recursive stack frame needs to track the fact that the result of the next call to the function is used to compute the larger expression that is then returned:

(cons (first l1)           (my-append (rest l1) l2))))
     ^ current element      ^ recursive call
^ combine to list for this level of the recursive stack

Next class, we'll dig more into how the call stack is important for functional programming.

# A bit more Racket basics: `cond` in favor of nested `if`

Write a function that returns 0 if numbers are equal, 1 if a > b, -1 if a < b.

(define (compare a b)
  (if (= a b)
      0
      (if (> a b)
          1
          -1)))

:::info
For A0, it's totally fine to use nested `if` statements. In future assignments, `cond` will be preferred.
:::

We can also use the `cond` syntax form to do something similar to if-elif-else blocks in other languages:

(define (compare a b)
  (cond
    ((= a b) 0)
    ((> a b) 1)
    (else -1)))

# Scope warmup

Now, let's turn back to the question of how languages specify *semantics*. We'll consider the meaning of a few similar programs in Python and Racket.

:::success
What is the result of the following Python program?

def f(x):
    y = 1
    return x + y
print(f(2) + y)

What about this similar Racket program?

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

:::

:::spoiler Think, then click!
Both produce errors, because the variable `y` is not _in scope_ at the `print` call in the final line.
:::

How is the scope of a variable defined?

To define variable scope, we need to zoom out to cover how to define the semantics of a language.

---

# Specifying semantics: evaluation rules for Racket

We can specify the *semantics* of a language construct (e.g., `if`, `+`, etc) via *evaluation rules*. In the formal study of programming languages, these are often provided via mathematical formulas (in particular, a type of formula known as an *inference rule*). Since we want to focus more on the principles of programming languages in practice than theory this semester, we will instead describe *evaluation rules* in natural language.

For the languages we study in this class, our evaluation rules themselves will be recursive. That is, even if the program we are describing does not have recursion, **how** we evaluate (run) the program is based on recursively applying the rules for each type of language construct.

---
Our first evaluation rule will be the simplest one: for *values*. We can think of this as one base case of the recursive evaluation rules.

:::info
**Racket ==evaluation== rule: value `v`**

A value, `v`, evaluates to itself.

This includes numbers `n` $\in \mathbb{Z}$, booleans `#t`/`#f`, etc.
:::

As a reminder: **values** are expressions that cannot be evaluated (reduced) any further _in their current form_.

Examples of values: `#t`, `#f`, `5`, `empty` `'(1 2)` `'(+ 1 2)`

:::warning
Note the quote symbol `'` stops evaluation, turning things inside the parens into values.
:::

`'(+ 1 2)` **is** a value, if we try to evaluate it in the current form, we get back the same thing.
`(+ 1 2)` (without the quote) **is *not*** a value, if we try to evaluate it in the current form, we get `3`, which is a value.

---
Our first *recursive* evaluation rule for Racket will be for the `if` special form.

:::info
**Racket ==evaluation== rule: `if` `(if e0 e1 e2)`**

- ==Evaluate== `e0` to value `v0`.
- If the value is "truthy" (see A0), ==evaluate== `e1`.
- Else ==evaluate== `e2`.
:::

Note that this rule for ==evaluate== references the definition of evaluate! This allows nested sub-expression to have meaning.

---
Here is another example of a recursive rule. Here, we are going to write one specific rule for `+`, though later, we'll see that the semantics for `+` can be understood as just one example of how functions are applied.

:::info
**Racket ==evaluation== rule: `(+ e1 ... en)`**

- ==Evaluate== `e1...en` to value `v1...vn`.
- The result is the mathematical sum of the values `v1...vn`.
:::

---

Now, we'll turn back to the evaluation rules related to *scope*.

Recall that **declarations**: bind variables to _values_.

`(define x e)`

Binds the variable `x` to the value produced by evaluating `e`.

`(define a 20)`
`(define b (+ 10 10))`

Binds the variable `a` to the value `20` and the variable `b` to the value `20` (bindings are to values, not expressions).

Bindings add information to the *dynamic environment*. The dynamic environment after these two bindings would be: `{ a -> 20, b -> 20}`.

What about when a variable is *used*? What is the meaning of `(+ x 1)`?

The answer depends on whether `x` has previously been defined in the environment!

How do we know the value of a variable?

We keep a dynamic environment:
- A sequence of bindings mapping identifier (variable
name) to _values_.
- “Context” for evaluation, used in evaluation rules.
- The dynamic environment starts "empty" in terms of user-defined bindings (it has only built-in language constructs). Expressions can add bindings to the dynamic environment for specific scopes.

E.g. `(define a 20)` binds `a` to `20` in the _global scope_.

:::info
**Racket ==evaluation== rule: variable use `x`**

- Check if `x` is in the current dynamic environment (which is built based on the variables currently in scope) as `{x -> v}`. If you find it, evaluate to `v`.
- Otherwise, report an error.
:::

:::success
Beyond `define`s, have we seen other Racket cases where variables are added to the dynamic environment?
:::

:::spoiler Think, then click!
Yes! Function calls also add their arguments to the dynamic environment when the body of the function is evaluated.
:::

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

- Check if `f` is a special form, for example `if` :star:, if so go to that rule. Otherwise, for now we will assume `f` is a function (and otherwise report an error). We know then elsewhere we have `(define (f a1 ... an) body)`.
- Otherwise, ==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 dynamic environment.
:::

# Scope: local bindings

It can also be useful to have local variables without having to use `define` blocks.

A `let` expression binds a set of variables for use in the body of the let block.

**Syntax:** `(let ([x1 e1] ... [xn en]) e)`

Note: interchangeable: `()`, `[]`, or `{}`

:::info
**Racket ==evaluation== rule: `(let ([x1 e1] ... [xn en]) e)`**
- Under the current environment, ==evaluate== `e1` through `en` to values `v1, ..., vn`.
- The result is the result of ==evaluating== `e` under the dynamic environment extended with bindings `x1 -> v1, ..., xn -> vn`.
:::

For example:

> (let ((x1 1)  ; binds x1 to 1 in body
        (x2 2)) ; binds x2 to 2 in body
    (+ x1 x2))  ; body
3

## Local bindings: `let*`

Sometimes, we want the expression of one binding to refer to a variable bound in a previous binding.

With `let`, this does not work, since the remaining bindings are _not_ part of the scope of variables.

(let ((x1 1)
      (x2 (* x1 2))) ; error, x1 undefined
  (+ x1 x2))

Instead, the syntactic form `let*` threads previous bindings through, allowing this expression to work:

(let* ((x1 1)
       (x2 (* x1 2))) ; Works to use x1
  (+ x1 x2))

See the Racket documentation for more on `let` vs. `let*` vs. `letrec`: https://docs.racket-lang.org/reference/let.html

## Group exercise using `let`/`let*`

:::success
Write a function `quadratic-roots` that takes three coefficients `a`, `b`, and `c` of a quadratic equation $a x^2 + b^x + c = 0$ and returns the roots as a list. If there are no _real_ roots, return the empty list.


Note: Racket can calculate with imaginary numbers, so the `sqrt` of a negative will not error. But for this problem, we want only the real roots.

Recall that if $b^2 - 4ac$ is negative, then the roots are imaginary.

- Use: `let`/`let*`, `sqrt`

Examples:

(quadratic-roots 1 -3 2)  ; Output: '(2 1)
(quadratic-roots 1 2 1)   ; Output: '(-1 -1)
(quadratic-roots 1 0 1)   ; Output: '()

:::

**Solution:**

:::spoiler Think, then click!
Note that the important piece is that the discriminant is only calculated once, but via the `let*`, is used multiple times. Many groups choose to `let`-define more pieces or not use `let` in building the list, that is fine.

(define (quadratic-roots a b c)
  (let* ((disc (- (* b b) (* 4 a c)))
         (sq (sqrt disc)))
    (if (< disc 0)
        `()
        (let ((root1 (/ (+ (- b) sq) (* 2 a)))
              (root2 (/ (- (- b) sq) (* 2 a))))
          (list root1 root2)))))

:::

Next class, we'll go over a more detailed example where local bindings can lead to far more efficient computation.