From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12631 invoked by alias); 17 Mar 2017 10:37:43 -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 12609 invoked by uid 89); 17 Mar 2017 10:37:42 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: Yes, score=5.1 required=5.0 tests=AWL,BAYES_00,FOREIGN_BODY1,KAM_LAZY_DOMAIN_SECURITY autolearn=no version=3.3.2 spammy=avez, H*Ad:U*kawa, vous, UNS X-HELO: smtps-n.oca.eu Received: from smtps-n.oca.eu (HELO smtps-n.oca.eu) (192.54.174.167) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 17 Mar 2017 10:37:40 +0000 Received: from [192.168.109.88] (natoca100-13.unice.fr [134.59.100.13]) by smtps-n.oca.eu (Postfix) with ESMTPSA id 005E380527; Fri, 17 Mar 2017 11:37:33 +0100 (CET) From: Damien MATTEI To: Per Bothner Subject: Re: StackOverflowError in a specialized map Date: Fri, 17 Mar 2017 10:37:00 -0000 User-Agent: KMail/1.9.6 Cc: Kawa mailing list References: <201703151608.33735.Damien.Mattei@unice.fr> In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="windows-1252" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Message-Id: <201703171137.33718.Damien.Mattei@unice.fr> X-IsSubscribed: yes X-SW-Source: 2017-q1/txt/msg00082.txt.bz2 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/LO= GIKI/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 t= he '() 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), >=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. no more success >=20 > However, if the stack overflow is in the final apply, that won't be enoug= h, > because that apply is not a tail-call (because of the cons of the result). >=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)) not available seems in scheme you cannot do @something only ,@something it exists only unquote-splicing >=20 > 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 re= st argument, > which it doesn't. >=20 > If you don't mind using set-cdr! that would be a relatively simple and ef= ficient 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 tel= l.) yes it is: (let ((lists (cons list1 more-lists))) Damien --=20 Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS