How to implement "if" in normal order in Scheme?

Question

I was learning SICP and I read about "the applicative order" and "the normal order". Then I played around the Exercise 1-6 and looked into the following code:

#lang racket
(define (p) (p))
(define (new-if test-expr then-expr else-expr)
  (cond (test-expr then-expr)
        (else else-expr)))

And when I evaluate (new-if (= 2 2) 5 (p)) , it goes into a dead loop because both the (= 2 2) and (p) are evaluated. So I wonder how to make this new-if in the normal order without changing the #lang racket into #lang lazy , but I can't figure it out.

> (new-if (= 2 2) 5 (p))
> 5

Answer 1

You cannot change the evaluation order of #lang racket. #lang lazy works since it is normal order. You can delay evalution with delay / force:

#lang racket

(define (p) (p))
(define (new-if test-expr then-expr else-expr)
  (cond ((force test-expr) (force then-expr))
        (else (force else-expr))))
(new-if (delay (= 2 2)) (delay 5) (delay (p))) ; ==> 5

Without side effects you can replace delay with wrapping in a no argument lambda (thunk) and change force to apply the procedure.

Answer 2

If we define new-if as a function:

(define (new-if test-expr then-expr else-expr) 
   ...)

Then in the program

 (define (p) (p))
 (new-if (= 2 2) 5 (p))

the form (new-if (= 2 2) 5 (p)) is a function call.

The functions call is evaluated in this order:

1. Evaluate new-if (evaluates to our new-if procedure)
2. Evaluate (= 2 2) (evaluates to true)
3. Evaluate 5 (evaluates to 5)
4. Evaluate (p) (leads to a loop)
5. Now the result of new-if is called with the arguments (the results from 2., 3. and 4.).

The problem is of course that we never get to 5. The evaulation of the (p) leads to an infinite loop before the body of new-if is evaluated.

This means, that no matter what we put in the body of new-if the call (new-if (= 2 2) 5 (p)) will always lead to an infinite loop.

In order words, in a language with normal order semantics, you can't define new-if as a normal function.

The intended evaluation order of (new-if e0 e1 e2) is:

1. Evaluate e0, let's call the result t.
2. If t is non-false, then evaluate e1
3. Otherwise t is false, so evaluate e2
4. The result is the either the result from 2. or from 3.

This order of evaluation is different from the order in a function call. So new-if must defined as a new form. The mechanism to define forms that use non-standard evaluation orders is define-syntax. It allows you to define new-if as a macro.

Answer 3

So I wonder how to make this new-if in the normal order ...

You can't. if is a special form provided by the host Scheme environment you're running code in. Other conditional syntax like cond and case are derived from if via macros in most implementations, a topic that IIRC the book doesn't touch on either using in early chapters introducing Scheme or implementing in the interpreters and compilers it focuses on in later chapters.

The purpose of exercise 1.6 is demonstrating why if has to be special and can't be implemented as a normal function; Eva Lu Ator is wrong and the definition of sqrt-iter using her new-if is an example of how it can fail.

Answer 4

Quick answer

As it is stated, the whole point of the exercise is too show that you cannot write new-if as a normal function if you use the application order evaluation. However the normal order evaluation permits it. So both order have advantages and drawbacks.

More details

The difference is that in the application order evaluation, you first evaluate all symbols (the function and the arguments) then you make the substitution, and in the normal order evaluation, you evaluation the first symbol (usually a function), proceeds to the substitution then evaluation again until you are reduced to a simple atom (a value).

So the application order evaluation can be seen as more efficient but you lacks a part of control.

Example

For example if you define f as

(define (f x) (* x x))

and you call (f (+ 1 2)), then the application order evaluation only computes a single time (+ 1 2), when the normal order evaluation computes it twice :

1. (f (+ 1 2)) % first call
2. (* (+ 1 2) (+ 1 2)) % f is substituted by its definition

Since * is primitive, the computation is made with 2 instances of (+ 1 2). So it is less optimal. There is a way to optimize this with laziness. The language Haskell uses laziness, and you can use it too in racket with #lang lazy. It is a normal order evaluation with a little addition (the laziness).

However the a normal order evaluation, it allows you to define

 (define (test x y) (if (= x 0) y 0))

since the expansion (the substitution of the function by its body) is made before the reduction (the computation that can leads to another evaluation of an expression).