Lecture_Scope

COMP 3007 - Winter 2025

• Instructor: Sean Benjamin

• Content Provided By: Dr. Andrew Runka

• Institution: Carleton University

Scope of the Lecture

• Topics Covered:

  • Procedural Abstraction on a Larger Scale: Square Roots using Newton’s Method

  • Scope

  • Block Structure

  • Special Form: let

  • When to use define vs let

• Learning Outcomes:

  • Understanding procedural abstraction, scope, and block structure

Problem: Computing Square Roots

• Definition:

  • Square root of x: ( ext{√}x = y ) implies ( y² = x )

• Newton's Method for Successive Approximations:

  1. Guess value for ( ext{√}x ).

  2. Enhance guess by averaging: ( rac{x}{y} + y )

  3. Conclude when ( y² \approx x ).

Example: Computing ( ext{√}2 )

• Iterative Process of Guesses:

  • Start with guess: 1.0

  • Quotient: 2.0

  • Average Approximations:

    • (1.0 + ( rac{2}{1.0} )) / 2 = 1.5

    • (1.5 + ( rac{2}{1.5} )) / 2 = 1.4167

    • Continue until close.

A Program Approach

• Key Idea:

  • Break down problem into subproblems utilizing a divide-and-conquer strategy.

• Procedural Abstraction:

  • The function user (e.g., sqrt x) does not need to see the internal workings.

Newton's Method Concept

• Problem Statement: How can we find square root iteratively without built-in functions?

• Steps:

  1. Begin with a guess.

  2. Refine guess using the formula: averaging with ( rac{x}{ ext{guess}} ).

  3. Stop when results are sufficiently close.

Core Procedures

• Definitions:

  • (define (square y) (* y y))

  • (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))

  • (define (average x y) (/ (+ x y) 2))

• Functionality:

  • square: Calculates the square of a number.

  • good-enough?: Determines if current guess is sufficiently accurate.

  • average: Computes the average of guesses.

Improving the Guess

• Function:

  • (define (improve guess x) (average guess (/ x guess)))

• Purpose: Returns a more accurate guess.

Recursive Iteration

• Function Defined:

  • (define (sqrt-iteration guess x) (if (good-enough? guess x) guess (sqrt-iteration (improve guess x) x))

• Key Points:

  • When good-enough? is true, returns guess; otherwise, recursively call with the improved guess.

Putting It All Together

• Final Procedure:

  • (define (sqrt x) (sqrt-iteration 1.0 x))

• Process:

  • Start with initial guess of 1.0 and refine repeatedly.

Procedural Decomposition Diagram

• Visual representation of how sqrt, sqrt-iter, good-enough?, and improve interact in Newton's Method code.

Formal Parameters & Their Role

• Example:

  • (define (improve guess x) (average guess (/ x guess)))

• Parameters: guess and x are bound within the function.

The Environment

• Global Structure:

  • Includes various defined functions such as sqrt, good-enough?, average, etc.

Free Variables

• Example:

  • (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))

  • square is free (defined elsewhere).

Understanding Scope

• Scope Example:

  • (define (average x y) ...) and its interaction with improve function where average is considered a free variable.

Internal Definitions & Block Structure

• Example Definition:

  • (define (sqrt x) (define (good-enough? guess) ...) (define (improve guess) ...) (define (sqrt-iter guess) ...) (sqrt-iter 1.0))

Before vs. After (Global vs. Local)

• Global Context:

  • Separate definitions before internalization of methods (e.g., good-enough?, improve).

• Internal Context:

  • Functions are defined within sqrt to enhance encapsulation.

Nested sqrt Implementation

• Nested Definitions:

  • Uses local functions like square, average, good-enough?, and their interrelations to find a square root.

Importance of Modularity

• Benefits:

  • Modularity allows procedures to act as black boxes devoid of external conflicts.

  • Renaming freedoms enable changes without impacting outside functionality.

Lexical Scope

• Environment Definition:

  • sqrt and its nested definitions can access outer variables.

Key Lessons about Block Structure

• Namespace Pollution:

  • Prevented through nesting.

• Block Structure:

  • Ensures that implementation details remain private.

let Special Form

• Description:

  • Used for local variable bindings with limited scope to the body of the let.

  • Ideal for temporarily naming intermediate values.

let Syntax

• Syntax structure:

  (let ((<var1> <exp1>)  
        (<var2> <exp2>)  
        ...  
        (<varN> <expN>))  
    <body>)  

• Lexical Scoping:

  • Variables exist only within <body>.

Example Usage of let in good-enough?

• Function Definition:

  • (define (good-enough? guess x) (let ((tolerance 0.0001) (difference (abs (- (square guess) x)))) (< difference tolerance)))

A Visual Example of let

• Definition:

  • (define (func1 x) (let ((a 4)) (+ x a)))

• Shows use of a single let effectively.

Practice with let

• Task:

  • Rewrite the improve procedure utilizing let to name intermediate expressions; test with (improve 1 3).

• Current procedure:

  • (define (improve guess x) (average guess (/ x guess)))

Example of Enhanced improve with let

• Improved Definition:

(define (improve guess x)  
  (let ((fraction (/ x guess)))  
    (let ((sum (+ guess fraction)))  
      (let ((avg (/ sum 2))) avg))))  

Explaining let*

• Definition:

  • (let* ((var1 exp1) (var2 exp2) ... (varN expN)) <body>)

Example Comparison: let vs. let*

• Case Studies:

(let ((a 2)  
      (b (+ a 3)))  
   (+ a b))  
// Will not work as 'b' cannot access 'a'. 
(let* ((a 2)  
       (b (+ a 3)))  
   (+ a b))  
// Works successfully giving values 2 and 5.  

Homework Assignment

• Task:

  • Rewrite improve procedure using let*, test with (improve 1 3).

  • Evaluate if let* is necessary.

Comparison of let and define

• Differences:

  • define: Creates global or top-level bindings.

  • let: Creates temporary local bindings.

• Use Cases:

  • Use let for temporary variables, define for constants or functions.

Additional Examples of Scope

• Incorrect Usage:

(define (useDef x)  
  (if (> x)  
      (begin  
        (define a 4)  
        (+ a x))))  

• Error: define: not allowed in an expression context.

• Correct Usage:

(define (useDef2 x)  
  (if (> x)  
      (let ((a 4))  
        (+ a x))))  

Summary of Key Topics

• Procedural abstraction: using Newton’s Method for square roots.

• Understanding scope and block structure in programming.

• Using let appropriately for local bindings.

• When to utilize define vs let for creating variables.

Next Steps

• Next Lecture: Focus on Recursion.

• Readings:

  • Procedures and the Processes They Generate, Chapter 1.2

• Homework: Complete Week 2 assignments.

Acknowledgments

• Thank You!

• Carleton University