Uses of improper lists?

General
1

This is likely a veeeery old question, but strangely I hadn't given much thought about it.

Do people use improper lists such as (a b c . d) with more than 2 elements? I don't remember ever seeing such a use case.

If not, wouldn't it be possible to just disallow constructing improper lists apart from pairs? That would make list? a constant-time check, and would avoid the need for many user-defined procedures to have to worry about improper lists.

2

One boring answer is that it’s used for representing function definitions with a rest argument :wink:

> (eval '(define (f x . y) (append y (list x))))
> (f 1 2 3) 
'(2 3 1)
1 Like
3

Right—I forgot that one indeed. I wish this was represented with a keyword instead
(define (f x #:rest y) (append y (list x))).

(edit) Oh but then that wouldn't work with apply so well I guess?

4

Just to make it explicit: the time used for list? is O(1) today.

For BC it is O(1) and for CS it is amortized O(1).

In BC pairs have an PAIR_IS_LIST flag.

The beginning of list? for BC looks like this:

int scheme_is_list(Scheme_Object *obj1)
{
  Scheme_Object *obj2;
  int flags;

  if (SCHEME_PAIRP(obj1)) {
    flags = SCHEME_PAIR_FLAGS(obj1);
    if (flags & PAIR_FLAG_MASK) {
      if (flags & PAIR_IS_LIST)
        return 1;
      else
        return 0;
    }
  } else if (SCHEME_NULLP(obj1))
    return 1;
  else
    return 0;
...

For CS you need to check the rumble layer:

5 Likes
5

@Laurent.O: #:rest could work, but this would affect user-introducing keyword arguments — you would need to reserve #:rest to avoid ambiguity — which is fine, but kinda weird.

@soegaard: the actual logic for amortized constant time is no longer in the rumble layer (and the comments there probably should be removed). It's become a primitive in Chez Scheme: https://github.com/racket/racket/commit/120082f3f922cf3a38756a8a3023ccaed6dfe894.

7 Likes
6

@soegaard For a little bit more context, amortized O(1) can still be significant:

#lang racket

(define N 100000000)

(let ()
  (define l (time (make-list N 'a)))

  (time (let loop ([l l])
          (if (empty? l) ; implies `list?`
            #true
            (loop (rest l))))))

(let ()
  (define l (time (make-list N 'a)))

  (time (let loop ([l l])
          (if (null? l)
            #true
            (loop (cdr l))))))

cpu time: 4719 real time: 4719 gc time: 4565  <-- make-list
cpu time: 8929 real time: 8929 gc time: 2 
#t
cpu time: 4273 real time: 4273 gc time: 4119  <-- make-list
cpu time: 178 real time: 178 gc time: 0
#t

Possibly this is testing more than list?, but I suspect it's the biggest offender anyway.

1 Like
7

https://github.com/racket/racket/issues/3109 might be related?

I think list? probably won’t get any faster, but it might be possible to eliminate many calls of list? entirely with a smarter compiler optimization.

8

Related indeed. In the program above, ideally, list? would be checked only once outside the loop. And indeed this would be fast:

(let ()
  (define l (time (make-list N 'a)))

  (time (list? l))

  (time (let loop ([l l])
          (if (null? l)
            #true
            (loop (cdr l))))))

cpu time: 4384 real time: 4385 gc time: 4224
cpu time: 286 real time: 286 gc time: 0
cpu time: 171 real time: 171 gc time: 0
#t

The compiler 'merely' needs to prove that l always remains a list after first testing the full list (which should follow from make-list in any case).

1 Like
9

I am surprised the difference is as large as it is.
(I am assuming you are using a version newer than the one sorawee points to).

Maybe the contract of rest and first should be changed to pair? instead of list?.