This is the mail archive of the
kawa@sourceware.org
mailing list for the Kawa project.
Re: StackOverflowError in a specialized map
really hard to solve, in a recursive way....
i have rewrite the function with as much possible of tail recursion but it fails again:
;; 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 (= a 2) '() (+ a b))) '() '(1 2 3) '(4 5 6)) -> '(5 9)
(define map-nil-iter
(lambda (function result list1 . more-lists)
(letrec ((some?
(lambda (fct list)
;; returns #t 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)
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)))))))))
;; (map-nil-iter-call + '(1 2 3) '(4 5 6)) -> '(5 7 9)
;; (map-nil-iter-call (lambda (a b) (if (= 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))))
the recursive call of map-nil-iter are no more encapsuled
have not try the --full-tailcalls options, will do it later....
Damien
Le Wednesday 15 March 2017 17:22:50 Per Bothner, vous avez écrit :
> 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.)
--
Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS