[bug #30070] multiple returns from map

[bug #30070] multiple returns from map

[Szavai Gyula]

URL:
  <http://savannah.gnu.org/bugs/?30070>

                 Summary: multiple returns from map
                 Project: Guile
            Submitted by: szgyg
            Submitted on: Mon 07 Jun 2010 06:23:03 PM GMT
                Category: None
                Severity: 3 - Normal
              Item Group: None
                  Status: None
                 Privacy: Public
             Assigned to: None
             Open/Closed: Open
         Discussion Lock: Any

    _______________________________________________________

Details:

; 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)





    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?30070>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/

[bug #30070] multiple returns from map

[Stefan Israelsson Tampe]

Follow-up Comment #1, bug #30070 (project guile):

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.

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?30070>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/

[bug #30070] multiple returns from map

[Andy Wingo]

Follow-up Comment #2, bug #30070 (project guile):

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.

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?30070>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/

Re: [bug #30070] multiple returns from map

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 1155 bytes --]

Yes a tail pointer was a mind slip . But I did
changed the final reverse! to the functional reverse in the srfi-1 version
of map
and doing that should be enough. You pay at most 2x time wise due to the
need to
allocate twice as many conses, But there is no need to introduce new stack
features
as far as I can see.

/Stefan


On Fri, Aug 12, 2011 at 11:03 PM, Andy Wingo <INVALID.NOREPLY@gnu.org>wrote:

> Follow-up Comment #2, bug #30070 (project guile):
>
> 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.
>
>    _______________________________________________________
>
> Reply to this item at:
>
>  <http://savannah.gnu.org/bugs/?30070>
>
> _______________________________________________
>  Message sent via/by Savannah
>  http://savannah.gnu.org/
>
>

[-- Attachment #2: Type: text/html, Size: 1643 bytes --]

Re: [bug #30070] multiple returns from map

[Andy Wingo]

On Sat 13 Aug 2011 17:56, Stefan Israelsson Tampe <stefan.itampe@gmail.com> writes:

> Yes a tail pointer was a mind slip . But I did
> changed the final reverse! to the functional reverse in the srfi-1 version of map
> and doing that should be enough.

Yes, however there is a performance penalty.  We should probably do that
for R6RS.  But long-term, we need a solution that does not impose a
performance penalty.  That solution is to map recursively instead of
iteratively.

Andy
-- 
http://wingolog.org/

Re: [bug #30070] multiple returns from map

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 900 bytes --]

Interestingly there is another option assuming some magic,

Consider:
(define (map f L)
   (clear-recurrent-flag)
   (let ((ret (let loop ((L L) (R '())) (if (pair? L) (loop (cdr L) (cons
(car L) R)) R))))
      (got-recurrent?
          (reverse  ret)
          (reverse! ret))))

/Stefan

On Sun, Aug 14, 2011 at 10:03 PM, Andy Wingo <wingo@pobox.com> wrote:

> On Sat 13 Aug 2011 17:56, Stefan Israelsson Tampe <stefan.itampe@gmail.com>
> writes:
>
> > Yes a tail pointer was a mind slip . But I did
> > changed the final reverse! to the functional reverse in the srfi-1
> version of map
> > and doing that should be enough.
>
> Yes, however there is a performance penalty.  We should probably do that
> for R6RS.  But long-term, we need a solution that does not impose a
> performance penalty.  That solution is to map recursively instead of
> iteratively.
>
> Andy
> --
> http://wingolog.org/
>

[-- Attachment #2: Type: text/html, Size: 1394 bytes --]

[bug #30070] multiple returns from map

[Andy Wingo]

Update of bug #30070 (project guile):

                  Status:                    None => Fixed                  
             Open/Closed:                    Open => Closed                 

    _______________________________________________________

Follow-up Comment #3:

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

Thanks for the report, Szavai.

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?30070>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/