Recursive range in Lisp adds a period?

Question

(define ..
  (lambda (start stop)
    (cond ((> (add1 start) stop) (quote ()))
          ((eq? (add1 start) stop) (sub1 stop))
          (else (cons start (.. (add1 start) stop))))))

I have defined a simple range function. The intent is for

(.. 1 5)  -->  (1 2 3 4)

Instead, a bizarre period is being added to my tuple and I have no idea why:

(.. 1 5)  -->  (1 2 3 . 4)

I don't understand why this is happening. Any help is appreciated

Answer 1

A list in Scheme is either the empty list () (also known as nil in some Lisps), or a cons cell whose car (also known as first) is an element of the list and whose cdr (also known as rest) is either the rest of the list (i.e., another list), or an atom that terminates the list. The conventional terminator is the empty list (); lists terminated by () are said to be "proper lists". Lists terminated by any other atom are called "improper lists". The list (1 2 3 4 5) contains the elements 1, 2, 3, 4, and 5, and is terminated by (). You could construct it by

(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 ())))))

Now, when the system prints a cons cell, the general case is to print it by

(car . cdr)

For instance, the result of (cons 1 2) is printed as

(1 . 2)

Since lists are built of cons cells, you can use this notation for lists too:

'(1 2 3 4 5) ==
'(1 . (2 . (3 . (4 . (5 . ())))))

That's rather clunky, though, so most lisps (all that I know of) have a special case for printing cons cells: if the cdr is a list (either another cons cell, or ()), then don't print the ., and don't print the surrounding parenthesis of the cdr (which it would otherwise have, since it's a list). So, if you're seeing a result like

(1 2 3 . 4)

it means you've got an improper list that is terminated by the atom 4. It has the structure

(1 . (2 . (3 . 4)))

Now the question is: where in your code did the list construction go awry? .. is always supposed to return a proper list, so let's look at the cases: The first case always returns a proper list (the empty list):

((> (add1 start) stop) (quote ()))

The second case looks like it can return something that's not a list (assuming that (sub1 stop) == (- stop 1)):

((eq? (add1 start) stop) (sub1 stop))

Now, if .. were functioning correctly, then the third case would always be returning a proper list (since (cons x y) is a proper list if y is):

(else (cons start (.. (add1 start) stop)))

Make your second case return a list and you should be all set.

Answer 2

Your expression (sub1 stop) needs to read (list (sub1 stop))

In order for cons to build up a proper list, the second element needs to be a list itself. Thus, your function .. should return a list of some type for every cond clause.