Why is cond a special form in Scheme, rather than a function?

Question

(defun triangle-using-cond (number)
  (cond 
    ((<= number 0) 0) ; 1st
    ((= number 1) 1)  ; 2nd
    ((> number 1)     ; 3rd
      ;; 4th
      (+ number
         (triangle-using-cond (1- number))))))

Things that I know about Cond

• It allows multiple test and alternative expressions
• It has pre-specified evaluation order. For instance, the first condition will always evaluated whether it is right or not

One thing that I cannot distinguish is that what makes cond different from a function!

Quinquennial

Your example is in Common Lisp, not Scheme nor Racket. Your question still stands though. – Accoucheur

This is about if, but is correct for cond as well: vepa.in/technology/why-is-if-a-special-form-in-scheme – Accoucheur

Answer 1

A function call (e0 e1 e2) is evaluated like this

1. e0 is evaluated, the result is (hopefully) a function f
2. e1 is evaluated, the result is a value v1
3. e2 is evaluated, the result is a value v2
4. The function body of `f` is evaluated in an environment in which
   the formal parameters are bound to the values `v1` and `v2`.

Note that all expressions e0, e1, and, e2 are evaluated before the body of the function is activated.

This means that a function call like (foo #t 2 (/ 3 0)) will result in an error when (/ 3 0) is evaluated - before control is handed over to the body of foo.

Now consider the special form if. In (if #t 2 (/ 3 0)) the expressions #t is evaluated and since the value non-false, the second expression 2 is evaluated and the resulting value is 2. Here (/ 3 0) is never evaluated.

If in contrast if were a function, then the expressions #t, 2, and, (/ 3 0) are evaluated before the body of is activated. And now (/ 3 0) will produce an error - even though the value of that expressions is not needed.

In short: Function calls will always evaluate all arguments, before the control is passed to the function body. If some expressions are not to be evaluated a special form is needed.

Here if and cond are examples of forms, that don't evaluate all subexpressions - so they they need to be special forms.

Salas

Note: Racket require left-to-right evaluation of function arguments - in R5RS the order is unspecified. – Salas

Answer 2

If cond were not a special form then the expression:

((> number 1)         ;;3rd
 (+ number (triangle-using-cond (1- number))))

would cause either:

• an infinite loop because triangle-using-cond would keep calling itself recursively via the tail call (triangle-using-cond (1- number)).

• or, the last expression would try to apply the value #f or #t as a function (which in a type-2 Lisp such as ANSI Common Lisp is possible, but not possible in a type-1 Lisp such as Racket or Scheme) and produce an error.

What makes cond a special form is that its arguments are evaluated lazily whereas functions in Scheme or Common Lisp evaluate their arguments eagerly.

Ml

Thank you guys for adding your great responses. – Quinquennial

@ben I've never heard the terms "type-1/type-2" Lisp. Could you elaborate on that? (Just curious what the distinction means.) – Toshiatoshiko

@phg Typically symbols in lisps map to values. Values can be conventional datatypes as well as functions. The \1\ in "lisp-1" describes a lisp with a single name space where the symbol foo can map to exactly one value of any type. The \2\ in "lisp-2" describes a lisp with two namespaces, one for "conventional" data-types and the other for functions. ANSI Common Lisp is a lisp-2 and so the symbol foo can map to an integer value in one namespace and to a function/procedure value in the second namespace. It will evaluate to one or the other based on it's position within the expression. – Ml

Ah, ok, that's something I'm familiar with, although I've never heard it being called like this. Thanks. – Toshiatoshiko

Answer 3

As already answered, all arguments to a call to some function f are evaluated before the result of applying f is computed. Does it however mean that cond, or if, or both should be special forms?

Well, first, if you have if, you can easily simulate a cond with nested tests. Conversely, if is just a degenerate form of cond. So you can say that it is sufficient to have one of them a special form. Let's choose if because it is simpler to specify.

So shall if be special?

It doesn't really need to...

If the underlying question is "is if expressible in terms of a smaller set of special forms?", then the answers is yes: just implement if in terms of functions:

(define true-fn (lambda (then else) (then)))
(define false-fn (lambda (then else) (else)))

Whenever you can return a boolean, you return one of the above function instead. You could for example decide to bind #t and #f to those functions. Notice how they call one of the two input parameters.

((pair? x) ;; returns either true-fn or false-fn 
  (lambda () (+ x 1))
  (lambda () x))

...but why code in lambda calculus?

Evaluating code conditionally is really a fundamental operation of computing. Trying to find a minimal special forms where you cannot express that directly leads to a poorer programming language from the perspective of the programmer, however "clean" the core language is.

From a certain point of view, the if form (or cond) is necessary because without them it becomes really hard to express conditional execution in a way that a compiler/interpreter can handle efficiently.

This document referenced by uselpa discuss using closures to implement if, and concludes:

However, the syntactic inconvenience would be so great that even Scheme defines if as a special form.

Throes

Thank you guys for adding your great responses. – Quinquennial