pos+ (value added to position) - ex 3.5 in “ANSI Common Lisp” (p57)

Question

The problem is to take a list of integers and map them to another list containing those integers added to their respective position in the list.

Example runs with required outputs:

> (pos+ '(1 1 1 1))
(1 2 3 4)
> (pos+ '(7 5 1 4))
(7 6 3 7)

We are required to develop three alternate solutions. One using recursion, one using iteration, and one using mapcar.

I present my solutions below and seek comments on style, best coding conventions & habits to adopt. Also the question of which solution is preferred for this particular case arises, including justification for the choice.

Observations (on which I seek discussion) are included as comments in the code.

;;; (1) Using recursion
(defun pos+ (lst)
  (pos-helper lst 0))
(defun pos-helper (lst n)
  (if (null lst)
      nil
      (cons (+ (first lst) n)
            (pos-helper (rest lst) (+ n 1)))))
;; Elegant, as recursion often is, but not a tail call (cant abandon stack frame), 
;; hence less efficient at scale (which may not matter).

;;; (2) With iteration
(defun pos+2 (lst)
  (do ((i 0 (+ i 1)))
      ((>= i (length lst)) lst)
      (setf (nth i lst) (+ (nth i lst) i))))
;; Fewer lines, but i have a feeling of disappointment to be learning lisp
;; and not be using a functional style. Q. Is that intuition well-placed?

;;; (3) With mapcar
(defun pos+3 (lst)
  (mapcar #'(lambda (x y) (+ x y))
          lst
          (range (length lst))))

;; This would be my 'most beautiful' solution except for one problem.
;; Could not find any built in range function. I found range [footnote 1] 
;; and pasted it here. The syntax doesn't look anything like CL to me!
(defun range (max &key (min 0) (step 1))
   (loop for n from min below max by step  ;; did the lisp alien write this?! :)
      collect n))

link to range function used above

Answer 1

For loop you can see the excellent book by P. Seibel “Practical Common Lisp”, available on-line, in particular chapter 7 and chapter 22.

Let’s start from the last function: the idea is ok, we can just simplify the function noting that (lambda (x y) (+ x y)) is nothing more than the original +:

(defun pos+3 (lst)
  (mapcar #'+ lst (range (length lst))))

For the first function, since an helper function is introduced, it could as well be used for tail-recursion, instead of normal recursion:

(defun pos-helper (lis n acc)
  (if (null lis)
      (reverse acc)
      (pos-helper (rest lis) (1+ n) (cons (+ (first lis) n) acc))))

(defun pos+ (lis)
  (pos-helper lis 0 nil))

where acc accumulates the result, which at the end must be reversed. Note that certain Common Lisp compilers transform the function in an iterative loop, so I do not know if this would be considered recursive. In that case, your version is ok (but note the idiomatic use of (1+ expression) instead of (+ expression 1)).

Then, for the second function, of course a loop version is much more readable (even if it is not so lispy :) :

(defun pos+2 (lis)
  (loop for i from 0 
        for x in lis
        collect (+ x i)))

If you prefer more parentheses, here is a variant (without modifying the original list):

(defun pos+2 (lis)
  (let ((result nil))
    (do ((i 0 (1+ i))
         (y lis (cdr y)))
        ((null y) (reverse result))
      (push (+ (car y) i) result))))

A final note about efficiency: the function pos3 is the less efficient one since it must generate a new list with the same length as the original one (and so the list must be scanned twice, in addition to doubling the memory footprint of the program). With a simple trick we could use mapcar and avoid creating a new list:

(defun pos+3 (lis)
  (let ((index -1))
    (mapcar (lambda (x) (+ x (incf index))) lis)))

Answer 2

General style remarks

• lst is more of a Scheme idiom, in Common Lisp you don't eat vowels but write directly list if your variable is a list (to be honest, some CL standard functions have weird names too).
• "Functional = Elegant" is somewhat true, but don't let purity blind you into ignoring perfectly good alternative approaches; it is often reasonable to have a purely functional interface implemented with local mutable state, for example. Building a fresh list and reversing it is a pure functional way to implement map, but that's not how you implement an efficient map function.

Tail-call elimination

For solution 1, you define a helper function; you can use a tail-recursive call if you add an accumulator parameter to hold the reversed result list. For example:

(defun pos+helper (list result position)
  (if list
      (pos+helper (rest list)
                  (cons (+ (first list) position) result)
                  (1+ position))
      result))

Note however that Lisp being dynamic, it is possible that you can at a later point redefine pos+helper to be another function, which prevents the compiler to automatically transform it as a loop. Consider for example the case where you want to trace an existing function: the original function is likely to be instrumented by wrapping it into another function, and then the recursive call is calling the resulting wrapper.

Whether I compile the above function with (optimize speed) declaration or not, I obtain different outputs with disassemble. When speed is not optimized, the recursive call is effectively a CALL, which grows the stack but allows for a redefinition of pos+helper. A simpler example:

(defun tester ()
  (sleep 2)
  (tester))

(ql:quickload :bordeaux-threads)
(bt:make-thread #'tester :name "tester")

I created a thread which calls tester, which contains a call to sleep to slow down the infinite recursion, to avoid stack overflows.

USER> (find "tester" (bt:all-threads) :test #'string= :key #'bt:thread-name)
#<SB-THREAD:THREAD "tester" RUNNING {100CC049F3}>

The thread is found in the list of all threads, which means it is alive and the function is effectively recursing infinitely. Now, if I redefine tester:

(defun tester () :done)

Then the thread is stopped:

USER> (find "tester" (bt:all-threads) :test #'string= :key #'bt:thread-name)
NIL

This is obviously implementation dependant, but if I declare the function to be optimized for speed, no amount of redefinition changes the behaviour of the function under test.

You have better control of this if you define your helper function locally:

(defun pos+ (list)
  (labels ((recurse (list result position)
             (if list
               (recurse (rest list)
                        (cons (+ (first list) position) result)
                        (1+ position))
               result)))
    (nreverse (recurse list nil 0))))

First, it hides the auxiliary function, which is after all an implementation detail; but most importantly, since the body of a function is static in the sense that you do not redefine parts of it at runtime, the compiler is able to infer that recurse is never going to change, and can do the tail-call elimination without additional hints (most compilers can do that easily, except on platforms like Java (ABCL) where this is not possible).

(opinion: tail-call elimination breaks the elegance of the purely functional approach by making you rearrange parameters to satisfy an implicit, particular case where calls can be converted as jumps; in other words, this is a hack. In languages that mandates tail-call elimination, this is less of a hack, but not necessarily elegant either.)

The portable way to implement a loop is to write a loop or higher-level functions.