[Sbcl-devel] mapcar and friends return lists

[Robert E. B. <bb...@sp...>]

I've noticed that Python does not understand that calls to mapcar, mapc,
mapcan, mapl, maplist, and mapcon always return results of type list:


    * (defun foo (f x y)
        (find x (mapcar (the function f) y)))

    ; in: LAMBDA NIL
    ;     (FIND X (MAPCAR (THE FUNCTION F) Y))
    ; --> NTH-VALUE MULTIPLE-VALUE-BIND LET 
    ; ==>
    ;   (SB-KERNEL:%FIND-POSITION X
    ;                             (MAPCAR (THE FUNCTION F) Y)
    ;                             NIL
    ;                             0
    ;                             NIL
    ;                             (SB-KERNEL:EFFECTIVE-FIND-POSITION-KEY NIL)
    ;                             (SB-KERNEL:EFFECTIVE-FIND-POSITION-TEST NIL NIL))
    ; 
    ; note: unable to
    ;         expand inline
    ;       due to type uncertainty:
    ;         The second argument is a SEQUENCE, not a LIST.
    ; 
    ; note: unable to
    ;         expand inline
    ;       due to type uncertainty:
    ;         The second argument is a SEQUENCE, not a VECTOR.
    ; compilation unit finished
    ;   printed 2 notes
    STYLE-WARNING: redefining FOO in DEFUN
    
    FOO
    * 


The root cause appears to be that calls to the list mapping functions are
source transformed early into tagbody loops.  The compiler then can't infer
the return type of the loop.  The patch below to src/compiler/seqtran.lisp
appears to remedy the problem.  It wraps "(the list ... )" around the loop,
so the compiler knows the loop produces a list.

The patch probably results in a run-time check for LISTness at the end of
all MAPCAR calls when code is compiled without optimization, but that may
not be a big problem, given that the inner loops of all the list mapping
functions use ENDP.

                                bob

====================

Index: src/compiler/seqtran.lisp
===================================================================
RCS file: /cvsroot/sbcl/sbcl/src/compiler/seqtran.lisp,v
retrieving revision 1.38
diff -c -r1.38 seqtran.lisp
*** src/compiler/seqtran.lisp	3 Feb 2003 15:41:49 -0000	1.38
--- src/compiler/seqtran.lisp	6 Feb 2003 20:11:37 -0000
***************
*** 32,52 ****
  	  (:nconc
  	   (let ((temp (gensym))
  		 (map-result (gensym)))
! 	     `(let ((,map-result (list nil)))
! 		(do-anonymous ((,temp ,map-result) . ,(do-clauses))
! 			      (,endtest (cdr ,map-result))
! 		  (setq ,temp (last (nconc ,temp ,call)))))))
  	  (:list
  	   (let ((temp (gensym))
  		 (map-result (gensym)))
! 	     `(let ((,map-result (list nil)))
! 		(do-anonymous ((,temp ,map-result) . ,(do-clauses))
! 			      (,endtest (cdr ,map-result))
! 		  (rplacd ,temp (setq ,temp (list ,call)))))))
  	  ((nil)
! 	   `(let ((,n-first ,(first arglists)))
! 	      (do-anonymous ,(do-clauses)
! 			    (,endtest ,n-first) ,call))))))))
  
  (define-source-transform mapc (function list &rest more-lists)
    (mapfoo-transform function (cons list more-lists) nil t))
--- 32,55 ----
  	  (:nconc
  	   (let ((temp (gensym))
  		 (map-result (gensym)))
!              `(the list
!                (let ((,map-result (list nil)))
!                  (do-anonymous ((,temp ,map-result) . ,(do-clauses))
!                                (,endtest (cdr ,map-result))
!                    (setq ,temp (last (nconc ,temp ,call))))))))
  	  (:list
  	   (let ((temp (gensym))
  		 (map-result (gensym)))
!              `(the list
!                (let ((,map-result (list nil)))
!                  (do-anonymous ((,temp ,map-result) . ,(do-clauses))
!                                (,endtest (cdr ,map-result))
!                    (rplacd ,temp (setq ,temp (list ,call))))))))
  	  ((nil)
!            `(the list
!              (let ((,n-first ,(first arglists)))
!                (do-anonymous ,(do-clauses)
!                              (,endtest ,n-first) ,call)))))))))
  
  (define-source-transform mapc (function list &rest more-lists)
    (mapfoo-transform function (cons list more-lists) nil t))