Re: StackOverflowError in a specialized map

["Sudarshan S Chawathe" <chaw@eip10.org>]

I wrote the following, which seems to work as desired (if I understand
the original motivation correctly) and seems simpler and more idiomatic
to me.

It also avoids the use of 'append', which would lead to quadratic
running time.  It also does not need the --full-tailcalls option to Kawa
(which figures out the simple case of tail call used).  It uses SRFI 1
for the 'any' procedure, but that dependency is easy to remove if
desired.

(import (srfi 1))

(define (map/remove-nulls proc . lsts)
  (let loop ((lsts lsts)
             (result '()))
    (if (any null? lsts)
        (reverse result)
        (loop (map cdr lsts)
              (let ((proc-result (apply proc
                                        (map car lsts))))
                (if (null? proc-result)
                    result
                    (cons proc-result
                          result)))))))

;; a few tests

(map/remove-nulls +  '(1 2 3) '(4 5 6))

(map/remove-nulls (lambda (a b) (if (= a 2) '() (+ a b))) '(1 2 3) '(4 5 6))

(length (map/remove-nulls (lambda (i j)
                            (if (even? i)
                                '()
                                j))
                          (iota (expt 10 6))
                          (iota (expt 10 7))))

Regards,

-chaw


> From: Damien MATTEI <Damien.Mattei@unice.fr>
> To: kawa@sourceware.org
> Subject: Re: StackOverflowError in a specialized map
> Date: Fri, 17 Mar 2017 12:38:40 +0100
> 
> this and only this version works and WITH --full-tailcalls:
> 
> Le Thursday 16 March 2017 11:54:48 Damien MATTEI, vous avez =E9crit=A0:
> > really hard to solve, in a recursive way....
> >=20
> > i have  rewrite the function with as much possible of tail recursion but =
> it fails again:
> >=20
> > ;; map-nil-iter : a map version that exclude nil results
> > ;; the same as map-with-lambdas but will exclude from the result list the=
>  '() result of function
> > ;;
> > ;; (map-nil-iter + '() '(1 2 3) '(4 5 6))  -> '(5 7 9)
> > ;; (map-nil-iter (lambda (a b) (if (=3D a 2) '() (+ a b))) '() '(1 2 3) '=
> (4 5 6)) -> '(5 9)
> > (define map-nil-iter
> >=20=20=20
> >   (lambda (function result list1 . more-lists)
> >=20
> >     (letrec ((some?
> > 	      (lambda (fct list)
> > 		;; returns #t if (function x) returns #t for=20
> > 		;; some x in the list
> > 		(and (pair? list)
> > 		     (or
> > 		      (fct (car list))
> > 		      (some? fct (cdr list)))))))
> >=20
> >=20=20=20=20=20=20=20
> >       ;; variadic map implementation terminates
> >       ;; when any of the argument lists is empty.
> >       (let ((lists (cons list1 more-lists)))
> > 	(if (some? null? lists)
> > 	    result
> > 	    (let ((funct-result (apply function (map car lists))))
> > 	      (if (null? funct-result)
> > 		  (apply map-nil-iter function result (map cdr lists))
> > 		  (apply
> > 		   map-nil-iter
> > 		   function
> > 		   (append result (list funct-result))
> > 		   (map cdr lists)))))))))
> >=20
> >=20
> > ;; (map-nil-iter-call +  '(1 2 3) '(4 5 6))  -> '(5 7 9)
> > ;; (map-nil-iter-call (lambda (a b) (if (=3D a 2) '() (+ a b))) '(1 2 3) =
> '(4 5 6))  -> '(5 9)
> > (define map-nil-iter-call
> >   (lambda (function list1 . more-lists)
> >     (apply map-nil-iter function '() (cons list1 more-lists))))
> >=20
> > the recursive call of map-nil-iter are no more encapsuled
> >=20
> > have not try the --full-tailcalls options, will do it later....
> 
> tested and it works=20
> 
> great!
> 
> got the idea from university course and i reread the chapter at page 27 of =
> second edition of
> SICP Structure and Interpretation of Computer Program (Abelson  adn Sussman=
> )about tail recursion .... explaining how to transform a recursion in an it=
> erative form using an accumulator to pass result on the factorial example...
> perhaps the first time i really read this strange old book i bought 25 year=
> s ago ...
> 
> hope it will works with other scheme too, seems in Scheme norm to transform=
>  tail call in iterations automatically when possible.
> damien
> >=20
> > Damien
> >=20
> >=20
> > Le Wednesday 15 March 2017 17:22:50 Per Bothner, vous avez =E9crit=A0:
> > > On 03/15/2017 08:08 AM, Damien MATTEI wrote:
> > > > Hello,
> > > >
> > > > i have a custom definition of map ( https://github.com/damien-mattei/=
> LOGIKI/blob/master/lib/map.scm at  line 392):
> > > >
> > > > ;; map-nil : a map version that exclude nil results
> > > > ;; the same as map-with-lambdas but will exclude from the result list=
>  the '() result of function
> > > > ;;
> > > > ;; (map-nil + '(1 2 3) '(4 5 6)) -> '(5 7 9)
> > > > (define map-nil
> > > >   (lambda (function list1 . more-lists)
> > > >     (letrec ((some? (lambda (fct list)
> > > > 		      ;; returns #f if (function x) returns #t for
> > > > 		      ;; some x in the list
> > > > 		      (and (pair? list)
> > > > 			   (or (fct (car list))
> > > > 			       (some? fct (cdr list)))))))
> > > >
> > > >       ;; variadic map implementation terminates
> > > >       ;; when any of the argument lists is empty.
> > > >       (let ((lists (cons list1 more-lists)))
> > > > 	(if (some? null? lists)
> > > > 	    '()
> > > > 	    (let ((funct-result (apply function (map car lists))))
> > > > 	      (if (null? funct-result)
> > > > 		  (apply map-nil function (map cdr lists))
> > > > 		  (cons funct-result
> > > > 			(apply map-nil function (map cdr lists))))))))))
> > > >
> > > > i use it in various project since many years and this times it create=
> s a java StackOverflowError on a big list (22527 elements),
> > >=20
> > > Not unexpected - you're recursing on a big list.
> > >=20
> > > > i'm not sure if it's only in kawa and java that the problem occur so
> > > > i'm near to code this function differently,
> > >=20
> > > Try compiling map-nil with --full-tailcalls.   That might do it.
> > >=20
> > > However, if the stack overflow is in the final apply, that won't be eno=
> ugh,
> > > because that apply is not a tail-call (because of the cons of the resul=
> t).
> > >=20
> > > You can also try replacing:
> > >=20=20=20=20=20
> > >      (apply map-nil function (map XXX))
> > >=20
> > > by splice-notation:
> > >=20
> > >      (map-nil function @(map XXX))
> > >=20
> > > However, I don't think that would be enough for Kawa to be able to inli=
> ne the tailcalls.
> > > That would require the splice argument to match up with the more-lists =
> rest argument,
> > > which it doesn't.
> > >=20
> > > If you don't mind using set-cdr! that would be a relatively simple and =
> efficient solution:
> > >=20
> > >    (if (not (null? funct-result))
> > >       (let ((new-cons (cons funct-result '()))
> > >           (if (null? last-pair)
> > >               (set! result new-cons)
> > >               (set-cdr! last-pair new-pair))
> > >           (set! last-pair new-cons))))
> > >=20
> > > Instead of using map, put the above snippet inside a for-each.
> > >=20
> > > (The list1 parameter seems strange, as it isn't used, as far as i can t=
> ell.)
> >=20
> >=20
> >=20
> 
> 
> 
> --=20
> Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS
>