CODEWITHSUNDEEP
schemeletrec
Flux
Flux

Reputation: 10930

Is letrec only meant for defining procedures?

Is Scheme's letrec only meant for defining procedures, especially recursive ones? I am asking because it appears to be possible to bind non-procedures using letrec. For example, (letrec ((x 1) (y 2)) (+ x y)). If Scheme's letrec is only meant for procedures, then why isn't its syntax constrained to allow procedures only?

Consider this use of letrec to define two mutually recursive procedures:

(letrec ((is-even? (lambda (n)
                     (let ((n (abs n)))
                       (if (= n 0)
                           #t
                           (is-odd? (- n 1))))))
         (is-odd? (lambda (n)
                    (let ((n (abs n)))
                      (if (= n 0)
                          #f
                          (is-even? (- n 1)))))))
  (is-even? 123))

If we use Common Lisp's LABELS instead of Scheme's letrec, these two mutually recursive procedures would be defined like this instead:

(labels ((even-p (n)
           (let ((n (abs n)))
             (if (= n 0)
                 t
                 (odd-p (- n 1)))))
         (odd-p (n)
           (let ((n (abs n)))
             (if (= n 0)
                 nil
                 (even-p (- n 1))))))
  (even-p 123))

If letrec is only useful for defining procedures, then why isn't its syntax constrained like that of LABELS to allow only procedures in its initialization forms?

Upvotes: 0

Views: 110

Answers (2)

ignis volens
ignis volens

Reputation: 9282

It is mostly useful for binding procedures, yes: the variables bound by letrec can't refer to their own bindings until afterwards, so something like

(letrec ((x (list x)))
  x)

Does not work: see my other answer.

However first of all it would be a strange restriction, in a Lisp-1 like Scheme, to insist that letrec can only be used for procedures. It's also not enforcable other than dynamically:

(letrec ((x (if <something>
                (λ ... (x ...))
                1)))
  ...)

More importantly, letrec can be used in places like this:

(letrec ((x (cons 1 (delay x))))
  ...)

which is fine, because the reference to the binding of x is delayed. So if you have streams, you can then do this:

;;; For Racket
(require racket/stream)

(letrec ((ones (stream-cons 1 ones)))
  (stream-ref ones 100))

Upvotes: 1

D&#250;thomhas
D&#250;thomhas

Reputation: 10073

It is useful for defining procedures, but it is not only for that.

The difference between let* and letrec is defined in the manual:

Like let, including left-to-right evaluation of the val-exprs, but the locations for all ids are created first, all ids are bound in all val-exprs as well as the bodys, and each id is initialized immediately after the corresponding val-expr is evaluated.

The order in which ids are bound is significant here, as let* would not be useful for defining mutually-recursive procedures: the first procedure would have an unbound id for the second procedure.

As your example comes directly from the manual I think you should see that CS information is often dense and terse when reading, but it does say very clearly what the difference is with letrec.

Upvotes: 0

Related Questions