Next: , Previous: , Up: srfi rec   [Index]


2.18.3 Rationale

General

Among the prominent features of the Scheme programming language as defined in [KCR1998] are the following:

Nevertheless Scheme does not provide a syntax for recursive evaluations with the properties of:

Example

Problem 1

Let us look at the factorial function. In mathematical notation this function is expressed as:

(F : N |--> 1,            if N = 0;
            N * F(N - 1), otherwise

This expression is a term and not a definition or proposition.

We investigate some approaches to express the factorial function in Scheme.

Solution 1

A solution to our problem was already provided in [Clinger1985] by the form named-lambda. An even earlier solution with a slightly different syntax was implemented in Kent Dybvig’s Chez Scheme system. Using this special form, we can denote the factorial simply by:

(named-lambda (F N)
  (if (zero? N)
      1
    (* N (F (- N 1)))))

This expression is a function term that denotes the factorial in the appropriate brevity.

However, the form named-lambda has been dropped from later versions of the Scheme Report. Also it is missing in state–of–the–art implementations such as Chez Scheme (6.0a) and MIT Scheme (7.7.0). (The latter actually knows a form named-lambda with different semantics.)

Problem 2

The constant stream of ones can be defined via:

(define S (cons 1 (delay S)))

As in the case of the factorial, we are able to define the recursive object at the price of spending an externally bound name. Remedying this with let or letrec leads to similar objections as above.

Solution 2

This particular case of the self–referential problem was solved by the rec form in [Clinger1985]. This form allows writing:

(rec S (cons 1 (delay S)))

This expression is non–imperative and does not introduce an external variable binding.

Also this form has been dropped from later versions of the Scheme Report. Moreover, from our point of view this form alone is not capable of solving Problem 1. The respective definition would look like:

(rec F
  (lambda (N)
    (if (zero? N)
        1
      (* N (F (- N 1))))))

This again does not seem quite as simple and intuitive as the mathematical notation.

Proposal

We therefore propose to implement the rec special form in a generalized way that combines the advantages of the named-lambda and rec forms. The factorial function could be written:

(rec (F N)
  (if (zero? N)
      1
    (* N (F (- N 1)))))

Next: , Previous: , Up: srfi rec   [Index]