Module 1 Extra Materials

Rules Relating To Scope

Scope formalizes the idea of where and how can someone define and use an identifier.
Scopes can be nested (that is, there is one scope inside of another scope).

So far, there are only two kinds of scopes:

• Global Scope: each program defines a scope. constants and function names are added to this scope when defined.
• Function Scope: each function definition creates a scope in the body, with the names of the parameters being defined inside the function scope.

Note that function scopes are nested within the global scope.

As long as there is no ambiguity in terms of what a name is referring to, the definition of an identifier (either function definitions, constant definitions, or arguments in the body of a function) is valid. the only case when such ambiguity exists is when there are two same identifiers being defined in the same scope.

To access the entity (either a function, a parameter, or a constant) that an identifier is bound to, Racket looks at the scope where this identifier is in and tries to find the entity bound:

• In the case the identifier is inside a function body in a function definition, Racket will first look for parameters having the same name.
• If Racket cannot find it, or the identifier is not in a function body, it will look at the global scope to see if there are function or constants defined with the same name.
• If Racket still cannot find it, give an error; the identifier is not defined.

For an extra practice:
Is the following code allowed in Racket or not? Why?

(define (f x) x)
(define (g f) (f 2))

Substitution: "Leftmost Innermost non-value"

While doing the substitution of racket expressions, I have mentioned "leftmost innermost non-value" repetitively, and some people seems to be confused about it. Here is a more detailed explanation.

Non-Value

So far, there are three kinds of Racket expressions:

• Values
• Constants
• Function applications

While values need not to be substituted, constants and function application all have to be substituted eventually (that means, not necessarily in one single step) to a value.

We are going to use the term "non-value" to denote any expression that is not a value.

Leftmost Innermost

These two words correspond to the constraints mentioned in Slide 51:

1. We first evaluate the arguments, and then apply the function to the resulting values. (innermost)
2. When we have the choice among two or more substitutions, we take the leftmost (first) one.

The first constraint states that before applying the function the arguments have to be values. Thus, if we have an function application, we have to make sure that the arguments are all values before using the function application rule (Slide 53).

Putting it in another way, if we have an expression that contains other non-value expressions inside (aside: expressions nested within another expression is often called sub-expressions), we need to perform substitution on the sub-expressions first. After all of the sub-expressions have been substituted to their values, we can then proceed substituting the expression itself.

Note: At this moment in the lecture, if an expression contains sub-expression(s), this expression must be a function application.

Also note that this process is recursive (you will see this word many times throughout the course). In this case, it means that if the sub-expression to be substituted is also a function application, we need to apply the same constraints as listed above. That is, if the sub-expression also contains some non-value sub-expressions as arguments, we need to make sure those arguments are substituted to values. As a result, in every single step, only the innermost expression that only have values as sub-expressions will be selected for substitution.

The second constraint means given a choice of different non-value sub-expressions as arguments (that means the sub-expressions are at the same level), we always choose the leftmost non-value sub-expression for substitution.

For example:

; This example is slightly different than the one presented in class.
(define (f x y) (+ (* x x) (* y y)))

(f (f 1 2) (f 2 1))
; In this example, we have two innermost non-value (sub-)expressions: 
;  (f 1 2) and (f 2 1).
; We choose to substitute (f 1 2) first, since it is the leftmost one.
=> (f (+ (* 1 1) (* 2 2)) (f 2 1))
; at this time the section A contains two innermost non-value expressions, so we
; choose the leftmost, that is, (* 1 1).
=> (f (+ (* 1 1) (* 2 2)) (f 2 1))
;        |-------A-----|
; in subsequent steps I'll use |---| to mark the expressions to be substituted.

=> (f (+ 1 (* 2 2)) (f 2 1))
;          |-----|
=> (f (+ 1 4) (f 2 1))
;     |-----|
=> (f 5 (f 2 1))
;       |-----|
=> (f 5 (+ (* 2 2) (* 1 1)))
;          |-----|
=> (f 5 (+ 4 (* 1 1)))
;            |-----|
=> (f 5 (+ 4 1))
;       |-----|
=> (f 5 5)
;  |-----|
=> (+ (* 5 5) (* 5 5))
;     |-----|
=> (+ 25 (* 5 5))
;        |-----|
=> (+ 25 25)
;  |-------|
=> 50

Tracing extra example

(define origin-x 0)
(define origin-y 0)
(define (f x y) (* (- x y) (- x y)))
(define (g x y a b) (sqrt (+ (f x a) (f y b))))
(define (dist-origin x y) (g x y origin-x origin-y))

(dist-origin 3 4)

I recommend you to try it yourselves first, then check your answer.

(dist-origin 3 4)
=> (g 3 4 origin-x origin-y)       ;; Remember, constants should be 
=> (g 3 4 0 origin-y)              ;; replaced one by one!
=> (g 3 4 0 0)
=> (sqrt (+ (f 3 0) (f 4 0)))
=> (sqrt (+ (* (- 3 0) (- 3 0))) (f 4 0)))
=> (sqrt (+ (* 3 (- 3 0))) (f 4 0)))
=> (sqrt (+ (* 3 3) (f 4 0)))
=> (sqrt (+ 9 (f 4 0)))
=> (sqrt (+ 9 (* (- 4 0) (- 4 0))))
=> (sqrt (+ 9 (* 4 (- 4 0))))
=> (sqrt (+ 9 (* 4 4)))
=> (sqrt (+ 9 16))
=> (sqrt 25)
=> 5