2017-March-16
Conditionals like the if-else construct are something that programmers take for granted these days. In Lisp, conditionals are expressions, i.e, they evaluate to produce a value.
John McCarthy invented the conditional if expression in the context of Fortran.
In his original Lisp, it appeared as the more general cond form.
Conditional expressions has the mandate on distinguishing those objects that should be treated as the logical true and false values. If you have programmed in a language like Java, you would expect only constants like true and false to be recognized as logical values. This need not be the case in Lisp. A Lisp may use more than one type of object to represent true and false. This can be a source of confusion for novice (or sometimes even for experienced) Lispers.
This post details on how three popular flavors of Lisp – Common Lisp, Scheme and Clojure – represent logical values. We will try to understand why these design decisions were made. We will also see how to write idiomatic conditional expressions in each of these Lisps.
In Common Lisp, the symbol nil is used to represent both the empty list and Boolean false. An empty list may, of course, also be written as () and evaluates to the same object as nil. All values other than nil (i.e the empty list) are considered true. Common Lisp conventionally uses the constant t to stand for true, when no other value makes more sense. The following REPL session shows all the various forms logical values can assume in Common Lisp:
clisp> (if nil 'yes 'no)
;; no
; The empty list and nil are represented by the same object.
clisp> (if '() 'yes 'no)
;; no
; The symbol literal nil also evaluates to logical false.
clisp> (if 'nil 'yes 'no)
;; no
; All values other than nil evaluates to logical truth,
; though the constant `t` is its canonical representation.
clisp> (if 100 'yes 'no)
;; yes
clisp> (if t 'yes 'no)
;; yes
Note: In code examples, clisp>, scheme> and clojure> stands for the input prompt of Common Lisp, Scheme and Clojure REPLs respectively.
The Common Lisp language specification requires nil to be the default value returned by conditional expressions.
clisp> (if (< 5 4) 'ok)
;; nil
clisp> (when (< 5 4) 'ok)
;; nil
A predicate (i.e a function that return a true or false answer) may return the empty list or nil for a negative answer. But the generally accepted practice in Common Lisp is to return nil to signal false. Although any object other than nil is considered true, t is generally used when there is no special reason to prefer one such object over another. To better understand the Common Lisp conventions on predicates, let's write one. The following function will return true only if the first element of the argument list is also a list.
clisp> (defun flistp (alist)
(if (null alist)
'()
(listp (car alist))))
clisp> (if (flistp '()) 'yes 'no)
;; no
clisp> (if (flistp '(1 2 3)) 'yes 'no)
;; no
clisp> (if (flistp '((1 2) 3)) 'yes 'no)
;; yes
;; The predicate 'listp' returns true for
;; the empty list, despite it being the logical
;; false value!
clisp> (if (flistp '(() 1 2 3)) 'yes 'no)
;; yes
Note: It's the naming convention in Common Lisp to end predicate names with the character `p`. It may appear strange that some of the built-in functions like `null` and `atom` do not follow this convention. These functions were part of earlier Lisp dialects and the designers of Common Lisp wanted to maintain some level of basic conformance with the Lisps of that time.
The first version of flistp works as expected but a stylistic improvement is possible. In the following rewrite, we omit an explicit negative answer, as nil is the default value of all conditional expressions.
clisp> (defun flistp (alist)
(when (not (null alist))
(listp (car alist))))
clisp> (if (flistp '()) 'yes 'no)
;; no
clisp> (if (flistp '(1 2 3)) 'yes 'no)
;; no
clisp> (if (flistp '((1 2) 3)) 'yes 'no)
;; yes
clisp> (if (flistp '(() 1 2 3)) 'yes 'no)
;; yes
Now you might be wondering why the designers of Common Lisp have overloaded nil with three different meanings – the empty list, the false value and the symbol nil. The reason lies deep in the long history of Lisp. Almost from the very beginning, Lisp used the symbol nil as the special object that marked the end of a list. The same value was used to check for false values returned by predicates – an "unfortunate and lighthearted decision" according to John McCarthy. As Common Lisp aimed to unify and standardize the popular Lisps that existed at the beginning of 1980s, it did not deviate too much from the fundamental way logical values were represented and interpreted. As Lisp is mostly about list processing, using the same object to represent false and the empty list led not just to optimal resource usage but also to some economy in code. As an example of this, consider the following function that returns the first sublist from its list argument:
clisp> (defun fsublist (alist)
(cond
((null alist) nil)
((listp (car alist)) (car alist))
(t (fsublist (cdr alist)))))
clisp> (fsublist '(1 2 (3 4) (5)))
;; (3 4)
clisp> (fsublist '(1 2 3 4 5))
;; nil
As the empty list is the same as logical false, fsublist can be used in a predicate position without performing special type conversion on its return value.
clisp> (let ((s (fsublist '(1 2 (3 4) (5)))))
(or s 'no-sublists))
;; (3 4)
clisp> (let ((s (fsublist '(1 2 3 4 5))))
(or s 'no-sublists))
;; no-sublists
Early Lisp implementers also found that assigning the false value to the empty list can bring in some efficiency as well. As most platforms provided a "jump if zero" instruction, conditional expressions can be optimally implemented by using address zero (0) to represent the false value (i.e, the empty list!).
While Common Lisp sticked to tradition, there was a nascent Lisp community more interested in elegance and clarity. Scheme programmers considered treating nil, false and the empty list as the same object as nonsense.
The designers of Scheme decided to use specific representations for Boolean values. Scheme encode true and false with the symbols #t and #f respectively. Note that the Scheme conditional expressions (if, cond, and, or) treat all values other than #f as true. That means, the empty list '() is also a truth value. Scheme distinguishes both the logical false (#f) and the symbol nil from the empty list. As per recent specifications, a Scheme implementation is not required to provide a name to denote the nil or null value.
scheme> (if '() 'yes 'no)
;; yes
scheme> (if #f 'yes 'no)
;; no
scheme> (> 5 4)
;; #t
scheme> (< 5 4)
;; #f
scheme> (and (> 5 4) 2)
;; 2
scheme> (and (> 5 4) (= 2 1))
;; #f
Unlike Common Lisp, the default value of conditional expressions is left unspecified by the Scheme standard.
scheme> (if (< 5 4) 'ok)
;; <an-implementation-dependent-value>
scheme> (if (> 5 4) 'ok)
;; ok
If we are to re-implement flistp in Scheme, we have to be explicit about the return values. Both implementations shown below are correct:
scheme> (define (flist? alist)
(if (null? alist)
#f
(list? (car alist))))
scheme> (define (flist? alist)
(and (not (null? alist))
(list? (car alist))))
scheme> (if (flist? '()) 'yes 'no)
;; no
scheme> (if (flist? '(1 2 3)) 'yes 'no)
;; no
scheme> (if (flist? '((1 2) 3)) 'yes 'no)
;; yes
Note: The Scheme naming convention is to end predicate names with a question mark (?). This convention is also followed by Clojure.
The following implementation of flist? is not portable because a Scheme implementation is free to use any value as the default of conditional expressions. It need not be #f.
;; This implementation is not portable.
(define (non-portable-flist? alist)
(if (not (null? alist))
(list? (car alist))))
When called with an empty list, this is how non-portable-flist? behaves in Chez Scheme:
scheme> (if (non-portable-flist? '()) 'yes 'no)
;; yes
Scheme programs should be explicit about the values of all logical expressions. This is demonstrated again in the following re-implementation of the fsublist procedure:
scheme> (define (fsublist alist)
(cond
((null? alist) #f)
((list? (car alist)) (car alist))
(else (fsublist (cdr alist)))))
scheme> (fsublist '(1 2 3 4 5))
;; #f
scheme> (fsublist '(1 2 (3 4) 5))
;; (3 4)
scheme> (let ((s (fsublist '(1 2 3 4 5))))
(or s 'no-sublists))
;; no-sublists
scheme> (let ((s (fsublist '(1 2 (3 4) (5)))))
(or s 'no-sublists))
;; (3 4)
Clojure treats both nil and false as logical false values. All other values, including the empty sequence, are treated as logical truths. Though false maps directly to Java's Boolean/FALSE static object, an object constructed by a call to (Boolean. false) is considered to be logical true! So the important point to keep in mind is – all values other than the constants nil and false are true. Conditional expressions return nil as their default value. Clojure's nil is the same object as Java's null and the main reason for its existence is interoperability with the JVM.
Without further ado, let us re-implement the flist? function in Clojure. As Clojure has the more general concept of a sequence, which need not always be a list, we will call this function fseq?.
To help with the implementation of fseq? we need a function to check if an object is in fact a sequence, or can be converted to one. An object is converted to a sequence with a call to the seq function. But this will raise an exception if the conversion cannot be performed. We want to translate this exception into the boolean false value. This is the job of the helper function, which we call safe-seq. The code for both safe-seq and fseq? follows:
clojure> (defn safe-seq [obj]
(try
(seq obj)
(catch Exception ex
nil)))
clojure> (defn fseq? [aseq]
(and (safe-seq aseq)
(safe-seq (first aseq))))
clojure> (if (fseq? []) 'yes 'no)
;; no
clojure> (if (fseq? [1 2 3]) 'yes 'no)
;; no
clojure> (if (fseq? [[1 2] 3]) 'yes 'no)
;; yes
Safe-seq also comes-in handy for re-implementing fsublist. (I renamed this function as fsubseq in Clojure).
clojure> (defn fsubseq [aseq]
(when (safe-seq aseq)
(if (safe-seq (first aseq))
(first aseq)
(fsubseq (rest aseq)))))
clojure> (fsubseq [1 2 3 4 5])
;; nil
clojure> (fsubseq [1 2 [3 4] 5])
;; [3 4]
clojure> (or (fsubseq [1 2 3 4 5]) 'no-subseqs)
;; no-subseqs
clojure> (or (fsubseq [1 2 [3 4] [5]]) 'no-subseqs)
;; [3 4]
This post explained how logical values are represented in various Lisps and some of the reasons behind those design decisions. Which Lisp got it right is debatable. While Common Lisp favored efficiency and tradition, Scheme valued clarity and elegance. (If I were to design a language, I would choose a path between Scheme and Clojure.)
I hope, after reading this post, you must be in a better position to appreciate the following quote from Abelson and Sussman:
"It's remarkable how much energy in the standardization of Lisp dialects has been dissipated in arguments that are literally over nothing: Should nil be an ordinary name? Should the value of nil be a symbol? Should it be a list? Should it be a pair?"
So let the arguments continue. The hapless novice can be left alone, still looking confused!