Question

Alyssa P. Hacker doesn't see why if needs to be provided as a special form. "Why can't I just define it as an ordinary procedure in terms of cond?" she asks. Alyssa's friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if: (define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause))) Eva demonstrates the program for Alyssa: (new-if (=2 3) 0 5) 5 (new-if (= 1 1) 0 5) 0 Delighted, Alyssa uses new-if to rewrite the s (define (sqrt-iter guess \(x\) ) (new-if (good-enough? guess \(x\) ) $$ \begin{array}{l}\text { guess } \\ \text { (sqrt-iter (improve guess } x \text { ) } \\ x) \text { ) }\end{array} $$ What happens when Alyssa attempts to use this to compute square roots? Explain.

Short answer

Alyssa's `new-if` causes infinite recursion in `sqrt-iter` due to both clauses being evaluated, unlike `if`.

Step-by-step solution

Understanding the problem

Alyssa wants to redefine the `if` construct using `cond` as `new-if`. This seems to work with separate test cases, but you need to see what happens when using `new-if` in a recursive function like `sqrt-iter` to calculate square roots.

Exploring the test cases

When calling `(new-if (= 2 3) 0 5)`, the result is `5` because `2` is not equal to `3`, so the else clause is executed. Similarly, `(new-if (= 1 1) 0 5)` returns `0` as the condition is true, and the then clause is executed. These results are expected for a normal if-condition statement.

Examining the `sqrt-iter` function

The `sqrt-iter` function is designed to improve the guess for the square root of a number `x`. It uses recursion: if `good-enough?` is true, return `guess`; otherwise, call `sqrt-iter` again with an improved guess. Alyssa replaces the `if` with `new-if`, without realizing that `new-if` behaves differently in a recursive context.

Analyzing `new-if` in recursion

Alyssa's `new-if` function is fundamentally a procedure. In Scheme, all the arguments to a procedure are evaluated before the procedure is applied. Thus, both the `then-clause` and `else-clause` will always be evaluated in `new-if`, regardless of the `predicate`. This is different from the built-in `if`, where only one clause is evaluated depending on the condition.

Understanding why `new-if` fails in recursion

Because both `then-clause` and `else-clause` are evaluated at each recursive call, the function never terminates. The `else-clause` calls `sqrt-iter` if `good-enough?` is false, which results in an infinite recursion because it doesn't wait for the condition to decide whether or not to evaluate the `else-clause`.

Key concepts

Conditional Expressions

Conditional expressions in programming allow decision-making within your code. They control which block of code should be executed based on certain conditions. In the Scheme programming language, the `if` statement is one of the most common conditional expressions. It allows execution branching based on a boolean condition.
A typical `if` expression in Scheme looks like this:

• `(if condition then-expression else-expression)`

Here’s how it works:

• If `condition` evaluates to true, `then-expression` is executed.
• If `condition` evaluates to false, `else-expression` is executed.

This selective execution helps in making decisions and is fundamental in controlling the flow of your program.

Scheme Programming Language

Scheme is a minimalist, multi-paradigm programming language. It's a functional language derived from Lisp, emphasizing simplicity and flexibility. Understanding Scheme helps students appreciate core programming concepts like recursion and higher-order functions.

• Simplicity: Scheme has a simple and compact syntax, making code easier to read and write.
• First-class functions: Functions can be used as arguments to other functions, returned as values from other functions, or assigned to variables.
• Recursion: Scheme supports recursion elegantly, providing a natural way to repeat computation over iterative approaches.

Understanding Scheme gives valuable insights into functional programming, which is becoming increasingly relevant today. It also teaches you how to think about problems and solutions in a different way compared to more imperative languages.

Procedures

In Scheme, procedures are similar to functions in other programming languages. They are blocks of code you can call by name to perform a specific task. Learning about procedures helps in organizing code to be more reusable and easier to understand.

• Defining a procedure: You use `(define (procedure-name parameters) body)` to create a function.
• Calling a procedure: Use the procedure name followed by its arguments in parentheses. E.g., `(procedure-name arg1 arg2)`

Procedures help you reduce code duplication by encapsulating repetitive logic. They make programs modular by breaking down complex tasks into simpler parts. This increases code readability and maintainability, which are important in both small scripts and large applications.

Recursion

Recursion is a key concept in functional programming and is supported naturally in Scheme. A recursive process is where a function calls itself to solve a problem.
In the `sqrt-iter` example, recursion is used to iteratively improve the guess for the square root.

• Base Case: The function should stop calling itself when it reaches a condition that provides a solution. For `sqrt-iter`, this happens when the guess is "good enough."
• Recursive Case: If not at the base case, the function calls itself with updated parameters to get closer to the solution.

Recursion is powerful but can be tricky. Each recursive call must bring the problem closer to a solution to avoid infinite loops, as seen with Alyssa's `new-if`. With practice, recursion becomes a natural and effective tool for solving problems involving repeated application of a procedure.