2.18.3 Rationale

General

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

• it has simple syntax;
• it encourages recursive definitions, e.g. by ensuring memory efficient tail recursion;
• it supports non–imperative programming.

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

• being as simple, intuitive and close to the mathematical standard notation as possible;
• allowing general recursion;
• being non–imperative.

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.

• The simplest way perhaps is as:

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

  But this expression is not a term. It binds the factorial function to the variable f. The expression itself may not occur in a syntactical context where a name of the factorial is required.

• We list several ways to express the factorial as a function term.

  1. (let ()
       (define (F N)
         (if (zero? N)
             1
           (* N (F (- N 1)))))
           F)
     

  2. (lambda (N)
       (let F ([N N])
         (if (zero? N)
             1
           (* N (F (- N 1))))))
     

  3. (letrec ([F (lambda (N)
                   (if (zero? N)
                       1
                     (* N (F (- N 1)))))])
       F)
     

  4. ((lambda (F)
        (F F))
      (lambda (G)
        (lambda (N)
          (if (zero? N)
              1
            (* N ((G G) (- N 1)))))))
     

  All these expressions define the factorial anonymously, not binding it to a variable. However, all these expressions are more verbose than it seems necessary and they are less intuitive than it seems desirable.

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)))))