Re: StackOverflowError in a specialized map

[Per Bothner <per at bothner dot com>]

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 creates a java StackOverflowError on a big list (22527 elements),

Not unexpected - you're recursing on a big list.

> 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,

Try compiling map-nil with --full-tailcalls.   That might do it.

However, if the stack overflow is in the final apply, that won't be enough,
because that apply is not a tail-call (because of the cons of the result).

You can also try replacing:
   
    (apply map-nil function (map XXX))

by splice-notation:

    (map-nil function @(map XXX))

However, I don't think that would be enough for Kawa to be able to inline the tailcalls.
That would require the splice argument to match up with the more-lists rest argument,
which it doesn't.

If you don't mind using set-cdr! that would be a relatively simple and efficient solution:

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

Instead of using map, put the above snippet inside a for-each.

(The list1 parameter seems strange, as it isn't used, as far as i can tell.)
--
	--Per Bothner
per@bothner.com   http://per.bothner.com/