bugGuile - Bugs: bug #30070, multiple returns from map

 
 

bug #30070: multiple returns from map

Submitter:  Szavai Gyula <szgyg>
Submitted:  Mon 07 Jun 2010 06:23:03 PM UTC
   
 
Category:  None Severity:  3 - Normal
Item Group:  None Status:  Fixed
Privacy:  Public Assigned to:  None
Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Wed 17 Aug 2011 09:29:38 PM UTC, comment #3: 

I have provided a multiple-return safe map in rnrs, replacing reverse! with reverse as Stefan suggested.

Thanks for the report, Szavai.

Andy Wingo <wingo>
Group administrator
Fri 12 Aug 2011 09:03:21 PM UTC, comment #2: 

Stefan, the tail pointer does preserve performance, but it does not preserve the R6RS invariant about multiple returns.

Szavai is right.  Perhaps we should provide some other definition of `map' within R6RS to satisfy this requirement.  However, a proper solution looks more like recursion than iteration, and to do that with arbitrary-sized lists will require Guile to implement extendable stacks, which is a significant hack.

Andy Wingo <wingo>
Group administrator
Fri 15 Jul 2011 10:45:07 AM UTC, comment #1: 

Using srfi-1 and vanilla guile gives the same erroneous behavior.

I couldn't locate the vanilla map definition in the source code but looking at srfi-1 revealed the problem.

Basically the map is a tail loop where the reversed list is built.
Then a reverse! is done to correct the list order. This is the root
of the problem. Just replacing reverse! with reverse fixes this bug but introduces a slight performance issue of the order of say 20%. and a double of amount of consing done in the algorithm.

It's possible to rewrite map using a tail pointer to get the correct behavior without penalties.

Stefan Israelsson Tampe <tampe>
Group Member
Mon 07 Jun 2010 06:23:03 PM UTC, original submission:  

; R6RS 11.9:
; "If multiple returns occur from map, the values returned by
; earlier returns are not mutated."

(display "\nGuile's broken map\n")

(define k #f)
(define result #f)
(define results '())
(set! result (map (lambda (x)
                    (if x x (call/cc (lambda (c)
                                       (set! k c)
                                       1))))
                  '(#t #f)))
(set! results (cons result results))
(write results)
(newline)
(if (< (cadr result) 5)
    (k (+ 1 (cadr result))))
(newline)

;;;;;;;;;;;

(display "Correct map implementation\n") ; regarding call/cc.

(define (map f xs)                  ; it isn't tail-recursive
  (if (null? xs) '() (cons (f (car xs)) (map f (cdr xs)))))

(define k #f)
(define result #f)
(define results '())
(set! result (map (lambda (x)
                    (if x x (call/cc (lambda (c)
                                       (set! k c)
                                       1))))
                  '(#t #f)))
(set! results (cons result results))
(write results)
(newline)
(if (< (cadr result) 5)
    (k (+ 1 (cadr result))))
(newline)

Szavai Gyula <szgyg>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by wingo (Posted a comment)
  • -email is unavailable- added by tampe (Posted a comment)
  • -email is unavailable- added by szgyg (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2011-08-17 wingo StatusNone Fixed
        Open/ClosedOpen Closed

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code