[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Gcl-devel] Re: sbcl nthcdr

From: Camm Maguire
Subject: [Gcl-devel] Re: sbcl nthcdr
Date: 13 Feb 2006 19:16:50 -0500
User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2

Greetings!  And thanks for the example!

Here is what I'm playing with for 2.7.0 at present:

(defmacro tp-error (x y)
  `(specific-error :wrong-type-argument "~S is not of type ~S." ,x ',y))

(defun smallnthcdr (n x)
  (declare (seqind n))
  (cond ((= n 0) x)
        ((atom x) (when x (tp-error x si::proper-list)))
        ((smallnthcdr (1- n) (cdr x)))))

(defun bignthcdr (n i s f) 
  (declare (seqind i))
  (cond ((atom f) (when f (tp-error f si::proper-list)))
        ((atom (cdr f)) (when (cdr f) (tp-error (cdr f) si::proper-list)))
        ((eq s f) (smallnthcdr (mod n i) s))
        ((bignthcdr n (1+ i) (cdr s) (cddr f)))))

(defun nthcdr (n x)
  (cond ((typep n 'seqind) (smallnthcdr n x))
        ((atom x) (when x (tp-error x si::proper-list)))
        ((atom (cdr x)) (when (cdr x) (tp-error (cdr x) si::proper-list)))
        ((and (integerp n) (plusp n)) (bignthcdr n 1 (cdr x) (cddr x)))
        ((tp-error n (integer 0)))))

(defmacro nth (n x) `(car (nthcdr ,n ,x)))

GCL has the ability to eliminate all of this extra code (in principle)
in the most common case of modest n and proper-list x, but it requires
parallel definitions in the compiler -- one thing I've always longed
for is an ability to define the full function, compile it once
somewhere, and then use *its definition itself* as a sort-of generic
compiler-macro, allowing simplifications using information gathered by
the compiler.  This is complicated somewhat by one's ability to write
a form which the compiler will know how to eliminate.  The (typep n
'seqind) branch, for example, is readily eliminated or used
exclusively at present given the appropriate declarations in the outer
scope.  The proper-list checks are not (at present) on the other hand
-- what is required is 1) a type-propagation rule indicating cdr on a
proper list returns an object of the same type, and 2) the use of some
special form (non-nil-atom x) in place of the 'atoms used above,
together with an additional branch added for the nil case.  Finally,
such a scheme is also complicated by GCL's inability (at present) to
convert tail recursive function definitions to do loops which are
inlinable by the compiler.  In other words, the way things are now,
one either has to carefully coordinate duplicate function descriptions
at several places within GCL, or restrict oneself to a very particular
set of idioms.  

Just talking out loud.  Will try to commit something tomorrow.

Take care,

Robert Boyer <address@hidden> writes:

> The following code seems to be pretty much the way that SBCL handles the
> BIGNUM and circular list issues for NTH (via NTHCDR).
> The code is reminiscent of the ANSI DOC example code for LIST-LENGTH, and how
> it checks for circularity.
> I know no proof that this algorithm is correct, not yet anyway.  No specific
> doubt that it is wrong, just haven't figured out the argument yet.
> ; The following code was swiped from SBCL and mangled a bit by Boyer.
> ; This algorithm assumes that there are not more than MOST-POSITIVE-FIXNUM
> ; distinct conses in a Lisp image.  It might well be better to change this
> ; algorithm so that in FAST-NTHCDR, a check for (ATOM RESULT) is made before
> ; doing the (CDR RESULT), with a quick-out of NIL if RESULT is EQ NIL and a
> ; nice error if RESULT is some other atom.  And what about careful CDRing in
> ; the final DO, while circularity is being considered?
> (defun nthcdr (n list)
>   (flet ((fast-nthcdr (n list)
>            (declare (fixnum n))
>            (do ((i n (1- i))
>                 (result list (cdr result)))
>                ((not (plusp i)) result)
>              (declare (fixnum i)))))
>     (typecase n
>       (fixnum (fast-nthcdr n list))
>       (t (do ((i 0 (1+ i))
>               (r-i list (cdr r-i))
>               (r-2i list (cddr r-2i)))
>              ((and (eq r-i r-2i) (not (zerop i)))
>               (fast-nthcdr (mod n i) r-i))
>            (declare (fixnum i)))))))
> Bob

Camm Maguire                                            address@hidden
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]