[r6rs-discuss] [Formal] Map returning twice

---
This message is a formal comment which was submitted to formal-comment_at_r6rs.org, following the requirements described at: http://www.r6rs.org/process.html
---
Name        : Andre van Tonder
Email       : andre at het.brown.edu
Type        : defect
Priority    : minor
Component   : Higher order list procedures
Version     : 5.92
Sections    : 9.11 (base document), 3 (standard libraries)
Dependencies: None
Summary:
--------
MAP (and possibly other higher-order procedures) should return a new list
not only the first time, but /every subsequent/ time, if it returns more than 
once.  Not doing so may cause inconsistent states in algorithms that use 
backtracking.
Discussion:
-----------
Consistent behaviour of MAP (and other higher order procedures that construct 
new lists) in cases where these return more than once, is important in 
algorithms that use backtracking.
For this to work correctly, MAP should allocate new list structure not only 
the first time, but /every subsequent/ time it returns.  Certain imperative 
implementations of MAP do not allocate new structure on subsequent returns, and 
may lead to inconsistent states in backtracking algorithms.
Here is an example:
(let ((resume #f)
       (results '()))
   (set! results
         (cons (map (lambda (x)
                      (call/cc (lambda (k)
                                 (unless resume (set! resume k))
                                 0)))
                    '(#f #f))
               results ))
   (display results)(newline)
   (if resume
       (let ((resume* resume))
         (set! resume #f)
         (resume* 1))))
With a careful implementation of MAP, a new list is returned every time, so 
that the displayed results are
   ((0 0))
   ((1 0) (0 0))
   ((1 1) (1 0) (0 0))
Some imperative implementations of MAP do not return a new list every 
time, so that an inconsistent result such as
   ((0 0))
   ((1 0) (0 0))
   ((1 1) (1 1) (0 0))
may be returned (here the first two lists are the same - the (1 0) of the 
second step has been SET-CDR!-ed).  Here is one such, otherwise 
reasonable-looking, implementation:
;; Imperative implementation that only returns
;; a new list the first time it returns:
(define (map f lst)
   (if (null? lst)
       '()
       (let ((result (list (f (car lst)))))
         (let loop ((pair result)
                    (tail (cdr lst)))
           (if (pair? tail)
               (let ((pair* (list (f (car tail)))))
                 (set-cdr! pair pair*)
                 (loop pair*
                       (cdr tail))))
           result))))
(While this problem was pointed out in a prior formal comment, that comment was 
not well formulated, and the formal response to that comment did not 
really address this particular issue.)
Recommendation:
---------------
Require that MAP (and other higher order preocedures that construct lists) 
return a new list every time in cases where it may return more than 
once.