Function evaluating to lambda cannot be used to define new function within scope

Question

In scheme you can define functions which return a lambda expression and use them to define new functions. For example, you can write this code

(define (pow-iter base exp r)
  (if (= exp 1)
      r
      (pow-iter base (- exp 1) (* base r))))

(define (pow exp)
  (lambda (base)
    (pow-iter base exp base)))

(define cubic (pow 3))

(cubic 2)

We have here a function pow which takes the exponent as argument and evaluates to a lambda function which evaluates to the nth power of the given base.

However, if we put that within a scope like this:

(define (do-cubic x)
  (define (pow-iter base exp r)
    (if (= exp 1)
        r
        (pow-iter base (- exp 1) (* base r))))

  (define (pow exp)
    (lambda (base)
      (pow-iter base exp base)))

  (define cubic (pow 3))

  (cubic x))

(do-cubic 2)

I get an error

pow: undefined; cannot use before initialization

Why does this error occur and is there any way to fix it without changing the logic of the program?

@Renzo You mean that it works in #!racket. In #!r5rs, even under RacketVM, it should fail. They are different languages. — Sylwester

soegaard soegaard · Accepted Answer · 2016-07-20T18:54:39

This program provokes the same error:

#lang r5rs
(let ()
  (define (foo x) (lambda (y) (+ 42 x)))
  (define bar (foo 1))
  (bar 2))

Output:
  foo: undefined;
  cannot use before initialization

The reason you get an error is that "internal definitions" are rewritten into a letrec expression all the bindings are in effect while their initial values are being computed, thus allowing mutually recursive definitions.

(letrec ((foo (lambda (x) (lambda (y) (+ 42 x))))
         (bar (foo 1)))
 (bar 2))

In R5RS the initialization expressions are evaluated in an unspecified order. This means that in the first snippet above it is possible for (define bar (foo 1)) to be evaluated before (define (foo x) ...). In other words the value of foo is needed before foo have been initialized.

In Racket (#lang racket) internal definitions use letrec*-semantics (i.e. the initialization expressions are evaluated in the order they appear in the code. Thus the program runs without errors.

Note also that the letrec in #lang racket corresponds to what letrec* does in "R5RS"-implementations.

For more information on letrec vs letrec* see the introduction of http://www.cs.indiana.edu/~dyb/pubs/letrec-reloaded.pdf

Function evaluating to lambda cannot be used to define new function within scope

1 Answers