Agenda for today

Warmup exercise

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

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

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?

Recap: language building blocks

Expressions: well-defined snippets of the language (as defined by the grammar).

Examples of expressions: 1 (+ 1 2) (define x 10)

We typically do not consider snippets of incomplete/invalid syntax to be an expression:
(+ 1, sqrt(1) are not Racket expressions.

Values: expressions that cannot be reduced any further in their current form

Examples of values: #t, #f, 5, empty '(1 2) '(+ 1 2)
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.

Declarations: bind variables to values.

(define a 20)

Binds the variable a to the value 20.

(define b (+ 10 10))

Also binds the variable b to the value 20 (bindings are to values, not expressions).

The enviroment after these two bindings would be: { a -> 20, b -> 20}.

Bindings

How do we know the value of a variable?

Keep a dynamic environment:
– A sequence of bindings mapping identifier (variable
name) to values.
– “Context” for evaluation, used in evaluation rules.

E.g. (define a 20) binds a to 20 in the global scope.

Recap: variable use

If we have a variable use x

Eval rules:

1. Check if x is in the current dynamic environment (which is built based on the variables currently in scope). If you find it, return the value it is bound to.
2. Otherwise, report an error.

Recap: function application

(f e1 ... en)

Eval rules:

1. Check if f is a special form, for example if .
2. Otherwise, eval e1 through en to values v1, ..., vn.
3. Eval the body of the function with the arguments bound to these values.

Elsewhere we have (define (f a1 ... an) body)

body is evaluated with { a1 -> v1, ..., an -> vn} added to the environment.

Local bindings

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

Eval rules:

1. Under the current environment, evaluate e1 through en to values v1, ..., vn.
2. The result is the result of evaluating e under the environment extended with bindings x1 -> v1, ..., xn -> vn.

> (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

Scope

The scope of a binding is the area of program that is evaluated while that binding is in environment. More on this soon.

Group exercise using let/let*

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

Solution:

Note that the important piece is that the discriminent 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)))
         (sqrt-disc (sqrt disc)))
    (if (< disc 0)
        `()
        (let ((root1 (/ (+ (- b) sqrt-disc) (* 2 a)))
              (root2 (/ (- (- b) sqrt-disc) (* 2 a))))
          (list root1 root2)))))

Syntactic sugar

Syntactic sugar is convenient syntax added to a language to make it easier to use, without changing the core language itself. It's called "sugar" because its an additive that makes our lives sweeter!

Syntactic sugar is:
– Static textual translation to existing features in the core language.
– i.e., not a new language feature.

Now that we have let, we can see that and and or can be seen as syntactic sugar! In particular, and and or are special syntactic forms that behave more like if than a normal function application.

Consider the Racket expression:

(and #f (/ 1 0))

What is the result here? There are (at least!) 3 different options a language could produce:

1. If and behaved like a normal function, we would expect (/ 1 0) to evaluate to an error.
2. If and behaved like the python you have seen, we would expect the output to be false.
3. If and in this language had strict static typing rules, we would expect the output to be a static error because of the mismatched types.

Racket does indeed go with option 1:

> (and #f (/ 1 0))
#f

These semantics of only needing to check the first argument if the value is falsey is also known as "short circuiting".

Rather than distinct definitions for and and or, we can treat them as syntactic sugar for if:

Desugaring
(and e1 e2) desugars to (if e1 e2 #f)
(or e1 e2) desugars to (let ([x1 e1]) (if x1 x1 e2))

Why does or not desugar to just (if e1 #t e2)? Experiment with the Racket interactions window to see why (hint: use non-booleans values for the expressions).

First class functions

In Racket, functions are values. We'll see this much more in the coming weeks!

Racket has first class functions: functions have all the rights and privileges of other values.

A function is a value because on its own, in its current form, it cannot be evaulated. A function needs to be applied in order to be further evaluated.

+ on its own is a function: it is a value.
(+ 1 0) is a function application: it is not a value; it can be evaluated to the value of 1.

A lambda expression defined a function:

(lambda (x y)   (+ x y))
;       ^ args  ^ body

is the function that adds its two arguments. Note that this function does not have a name: it is an anonymous function.

It turns out that the function definition syntax we've been using so far is really just syntactic sugar for a variable binding to a lambda!

(define (fn x) (...)) is really sugar for
(define fn (lambda x) (...))!

Let's see an example of using a local binding for a lambda used inside of a function.

More local binding:letrec

Combing let and recursion can be tricky: can a local binding refer to itself? let itself cannot, but another form can!

Racket has another local binding construct for this reason: letrec.

To motivate this, let's first define a basic recursive function to reverse a list (without local bindings).

(define (reverse str) 
  (if (empty? lst)
      ; base case: reverse of empty string is empty string
      '()
      ; recursive case: the current head comes after the revered
      ; rest of the list. We have no function to add at the
      ; end of the list, but we can use append
      (append (reverse (rest lst)) (list (first lst)))))

Unfortunately, while this implementation is straightforward to write, it's inefficient.

What's the O(...) runtime for a list of length n?

Well, as we saw when we implemented it, append needs to recur through the length of its first argument. We are calling append on every call.

If a list has 1,00 items, then in the first call we pass append a first arg with length 999, then the second call on with length 998, and so on… this is

To do this, we'll use a trick we see more of as we go forward in this class: we'll add additional arguments to a recursive helper to track additional context. Often, this will be in an accumulator style pattern.

To show the use of letrec, we'll define out helper as a lambda and bind the variable helper to its definition.

The intuition behind this implementation is that helper will take two arguments: the list itself, which shrinks on every recursive call, and a new argument for the accumulator acc, which starts empty and grows on each recursive call. The base case of the recursion can then just return the acc, which has accumulated the fully reversed list by the time we get to the end.

(define (reverse lst)
  (letrec
      ((helper
        (lambda (lst acc)
          (if (empty? lst)
              acc
              (helper (rest lst) (cons (first lst) acc))))))
    (helper lst '())))

• Helper uses an accumulator (acc) to store the reversed list.
• Instead of appending (which is expensive), it builds the new list one cons cell at a time (cheap! constant time!)

We'll cover this example in more detail, including walking through examples, at the start of next class.