From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 39276 invoked by alias); 15 Mar 2017 16:23:04 -0000 Mailing-List: contact kawa-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: kawa-owner@sourceware.org Received: (qmail 39264 invoked by uid 89); 15 Mar 2017 16:23:04 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.5 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.2 spammy=cdr, fct, car, xxx X-HELO: aibo.runbox.com Received: from aibo.runbox.com (HELO aibo.runbox.com) (91.220.196.211) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 15 Mar 2017 16:23:01 +0000 Received: from [10.9.9.210] (helo=mailfront10.runbox.com) by mailtransmit03.runbox with esmtp (Exim 4.86_2) (envelope-from ) id 1coBhT-0002oe-NU; Wed, 15 Mar 2017 17:22:59 +0100 Received: from 70-36-239-163.dsl.dynamic.fusionbroadband.com ([70.36.239.163] helo=localhost.localdomain) by mailfront10.runbox.com with esmtpsa (uid:757155 ) (TLS1.2:DHE_RSA_AES_128_CBC_SHA1:128) (Exim 4.82) id 1coBhN-0007J5-32; Wed, 15 Mar 2017 17:22:53 +0100 Subject: Re: StackOverflowError in a specialized map To: Damien MATTEI , Kawa mailing list References: <201703151608.33735.Damien.Mattei@unice.fr> From: Per Bothner Message-ID: Date: Wed, 15 Mar 2017 16:23:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.7.0 MIME-Version: 1.0 In-Reply-To: <201703151608.33735.Damien.Mattei@unice.fr> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2017-q1/txt/msg00076.txt.bz2 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/