Lisping in style

Hello all,

I'm a complete CL newb, working my way through PCL, and doing some little coding projects on my own with the things I learn.

One of the hardest battles I'm fighting is trying to break the habit of trying to write things imperatively. I actually find it easier to do this in Scheme, since you really are pushed to do things recursively (I've worked my way through The Little Schemer, too). I'm still getting a feel for how to write things in idiomatic CL - I suspect I'm currently writing idiotic CL.

I was wondering if anyone would be willing to critique this little sample piece of code for overall style. It's a utility function for generating a series of lists according to a certain policy.

EDIT: This code is buggy.

;; This one is supposed to be a bit more fair.
;; The current "order" is defined as the largest index which is currently allowed
;; All combinations of order N are tried before any of order N+1
(defun get-next-prec-balanced (q limits)
  (let ((p (copy-seq q))
        (len (length q))
        (order (loop for idx in q maximizing idx))) ; *FIXME* this prevents us from using arrays
    (dotimes (n len)
      ;; If we haven't reached a hard limit or current order, increment & return
      (when (< (elt p n)
               (min (elt limits n) order))
        (if (> order (loop for idx in p maximizing idx))
            (setf (elt p n) order)
            (incf (elt p n)))
        (return-from get-next-prec-balanced p))
      ;; If we've reached the current order in the last elt, increase order
      (when (and (= (elt p n) order)
                 (= n (- len 1)))
        ;; Clean all the things!
        (dotimes (m len)
          (setf (elt p m) 0))
        ;; Set the first index whose limit is < the current order to the New Order
        (dotimes (m len)
          (when (< order (elt limits m))
            (setf (elt p 0) (+ order 1))
            (return-from get-next-prec-balanced p)))
        ;; Order is greater than each limit; we're done
        (return-from get-next-prec-balanced ()))
      ;; Otherwise, roll over to 0, which will carry to next position in dotimes loop
      (setf (elt p n) 0))
    (setf p ())
    (return-from get-next-prec-balanced p)))

(If you care, the purpose of the function is to generate indices into a set of other lists. I want to iterate over permutations of the elements of each list, but rather than do it as nested loops, I want to iterate over those permutations containing the first elements in all the lists, rather than the later ones. The iteration function uses this to generate the next permutation)

My last attempt was buggy.

(defun get-next-prec-balanced (q nums-elements)
  (let* ((p (copy-seq q))
         (len (length q))
         (order (loop for idx in q maximizing idx))
         (hard-limits (mapcar (lambda (x) (1- x)) nums-elements))
         (order-limits (mapcar (lambda (x) (min order x)) hard-limits)))
    (dotimes (n len)
      (if (< (elt p n) (elt order-limits n))
          (progn
            (incf (elt p n))
            (when (< (loop for idx in p maximizing idx)
                     order)
              (do ((j 0 (1+ j)))
                  ((>= (elt hard-limits j) order)
                   (setf (elt p j) order))))
            (return-from get-next-prec-balanced p))
          (progn
            (setf (elt p n) 0))))
    (dotimes (n len)
      (setf (elt p n) 0))
    (incf order)
    (dotimes (n len)
      (when (<= order (elt hard-limits n))
        (setf (elt p n) order)
        (return-from get-next-prec-balanced p)))
    (return-from get-next-prec-balanced nil)))

Is this question too vague?

Or does no one have the heart to tell me just how off-track I am... :/

Well, sorry for not seeing your code before, I didn't have time to answer your question.

There are few things that I can comment on.

If your intention is only to work with lists, then using ELT is not quite the best idea. As a general rule, it's more convenient to access the elements in a row (e.g. using DOLIST). In your case, since you are constructing a new list, you can use (loop for *** in *** ... collect *** ....) or some other method of collecting elements into a list instead of using (SETF ELT).

If your intention is to make a function that works with vectors as well, then it's ok to use elt, but keep in mind that the function will be assintotically slower when working with lists. Besides, using (SETF ELT) doesn't sound a good idea. You may consider to use the function MAP in this case: it's general (it works with any kind of sequence) and you can avoid these problems.

Also, you certainly don't need to use it at the end of the function, writing just NIL is sufficient if you want to make it clear that NIL is the default return value.

Thanks so much, gugamilare, that's exactly the kind of commentary I was hoping for. Thanks for taking the time.

gugamilare wrote:If your intention is only to work with lists, then using ELT is not quite the best idea. As a general rule, it's more convenient to access the elements in a row (e.g. using DOLIST). In your case, since you are constructing a new list, you can use (loop for *** in *** ... collect *** ....) or some other method of collecting elements into a list instead of using (SETF ELT).

Because random ELT access for lists is O(n), you mean? So iterating the whole list is O(n^2)? You're right - random access on a list doesn't seem like such a good idea in retrospect. And there I was congratulating myself on trying to be general.

Is an ELT access O(1) on an array?

Is AREF faster than ELT? If not, why would you use it?

gugamilare wrote:If your intention is to make a function that works with vectors as well, then it's ok to use elt, but keep in mind that the function will be assintotically slower when working with lists. Besides, using (SETF ELT) doesn't sound a good idea. You may consider to use the function MAP in this case: it's general (it works with any kind of sequence) and you can avoid these problems.

It wasn't obvious to me how to do the increment logic using just sequential access - if you notice, I'm not always referencing by the same index. There may be a simpler way of doing this hiding in there that will allow me to do so.

gugamilare wrote: Also, you certainly don't need to use it at the end of the function, writing just NIL is sufficient if you want to make it clear that NIL is the default return value.

Damn, I should have spotted that one on my own...

Thanks again - much appreciated!

garethw wrote:Is an ELT access O(1) on an array?

Yes.

garethw wrote:Is AREF faster than ELT? If not, why would you use it?

It depends on the compiler. If the compiler knows that the sequence is a vector, it can substitute ELT with AREF. Some compilers can infer the type of the object (e.g. SBCL) depending on the code around it. Even in these cases, using AREF might give the function a little speed, since by using it you are telling the compiler (and anyone reading the code) that the sequence you are using is intended to be a vector.

As a general rule, use AREF when you know that the sequence is a vector and you are quite sure you don't need to generalize it.

garethw wrote:It wasn't obvious to me how to do the increment logic using just sequential access - if you notice, I'm not always referencing by the same index. There may be a simpler way of doing this hiding in there that will allow me to do so.

Well, if it makes things easier and you are not that worried about speed, it's ok to use ELT. However, if you are doing this as an exercise, then you should find a better way.

garethw wrote:Thanks again - much appreciated!

You are welcome