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

 
 

bug #30070: multiple returns from map

Submitted by:  Szavai Gyula <szgyg>
Submitted on:  Mon 07 Jun 2010 06:23:03 PM UTC  
 
Category: NoneSeverity: 3 - Normal
Item Group: NoneStatus: Fixed
Privacy: PublicAssigned to: None
Open/Closed: Closed

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

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>
Project 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>
Project 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>
Project 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 File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 2 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Wed 17 Aug 2011 09:29:38 PM UTCwingoStatusNone=>Fixed
      Open/ClosedOpen=>Closed

    Back to the top


    Powered by Savane 3.1-cleanup1