From: Robert E. B. <bb...@sp...> - 2003-02-06 20:59:22
|
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)) |
From: Alexey D. <ade...@co...> - 2003-02-07 04:03:06
|
Hello, "Robert E. Brown" <bb...@sp...> writes: > I've noticed that Python does not understand that calls to mapcar, mapc, > mapcan, mapl, maplist, and mapcon always return results of type > list: What about (mapcan (lambda (x) x) (list 1))? > 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. Isn't it more correct to wrap TRULY-THE around the result of source transformation for all functions? -- Regards, Alexey Dejneka |
From: Robert E. B. <bb...@sp...> - 2003-02-07 20:53:39
|
The Hyperspec implies that MAPCAN and MAPCON return lists, but Alexey and Paul correctly point out that they can return anything: (mapcan #'identity (list 1)) ==> 1 (mapcon (constantly 1) (list 2)) ==> 1 Interestingly, CLISP returns NIL for both of the expressions above, so I've sent a bug report about it to the CLISP mailing list. I tried wrapping TRULY-THE around the result of each source transform instead of using THE, but it didn't work. The compiler still issues optimization notes, implying it does not know that MAPCAR and friends return lists. I don't know why. Here is an updated patch that treats MAPCAN and MAPCON differently from the rest. bob ==================== Index: src/compiler/fndb.lisp =================================================================== RCS file: /cvsroot/sbcl/sbcl/src/compiler/fndb.lisp,v retrieving revision 1.57 diff -c -r1.57 fndb.lisp *** src/compiler/fndb.lisp 3 Feb 2003 15:41:49 -0000 1.57 --- src/compiler/fndb.lisp 7 Feb 2003 20:02:59 -0000 *************** *** 133,140 **** (defknown (mapcar maplist) (callable list &rest list) list (call)) ! ;;; According to CLHS the result must be a LIST, but we do not check ! ;;; it. (defknown (mapcan mapcon) (callable list &rest list) t (call)) --- 134,142 ---- (defknown (mapcar maplist) (callable list &rest list) list (call)) ! ;;; Mapcan and mapcon can return any value, not just lists: ! ;;; (mapcan #'identity (list 1)) ==> 1 ! ;;; (mapcon (constantly 1) (list 2)) ==> 1 (defknown (mapcan mapcon) (callable list &rest list) t (call)) 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 7 Feb 2003 20:03:08 -0000 *************** *** 39,52 **** (: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)) --- 39,54 ---- (: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)) |
From: Paul F. D. <di...@dl...> - 2003-02-07 04:44:59
|
Robert E. Brown wrote: > I've noticed that Python does not understand that calls to mapcar, mapc, > mapcan, mapl, maplist, and mapcon always return results of type list: The results of MAPCAN and MAPCON aren't necessarily lists (look at the definition of NCONC: the last argument can be of any type.) Paul |
From: Christophe R. <cs...@ca...> - 2003-02-07 09:04:48
|
Alexey Dejneka <ade...@co...> writes: > > 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. > > Isn't it more correct to wrap TRULY-THE around the result of source > transformation for all functions? I /think/ so. I'm trying to think of a corner case, something like (but not exactly, because it's in fact a regular transform, not a source-transform: (define-source-transform + (arg1 arg2) (if (zerop arg2) arg1 (values nil t))) [ to fold an arg equal to zero ]. Then, wrapping TRULY-THE unconditionally would lose, because arg1 need not a priori be a number. So, if we do want to wrap TRULY-THE, I think I would want to be clearer about the responsibilities of the body of a source transform. Cheers, Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge) |
From: Alexey D. <ade...@co...> - 2003-02-10 12:33:15
|
Christophe Rhodes <cs...@ca...> writes: > Alexey Dejneka <ade...@co...> writes: > > > > 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. > > > > Isn't it more correct to wrap TRULY-THE around the result of source > > transformation for all functions? > > I /think/ so. I'm trying to think of a corner case, something like > (but not exactly, because it's in fact a regular transform, not a > source-transform: > (define-source-transform + (arg1 arg2) > (if (zerop arg2) > arg1 > (values nil t))) > [ to fold an arg equal to zero ]. > > Then, wrapping TRULY-THE unconditionally would lose, because arg1 need > not a priori be a number. So, if we do want to wrap TRULY-THE, I > think I would want to be clearer about the responsibilities of the body > of a source transform. If we also wrap THEs around arguments, (+ ARG) will be transformed into (TRULY-THE NUMBER (THE NUMBER ARG)), which, I think, should have the desired effect (with the current implementation of TRULY-THE it does not, what, I think, is confusing). -- Regards, Alexey Dejneka |