From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 78028 invoked by alias); 17 Mar 2017 11:38:44 -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 78016 invoked by uid 89); 17 Mar 2017 11:38:43 -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, H*r:sk:kawa@so, vous 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 11:38:42 +0000 Received: from [192.168.109.88] (natoca100-13.unice.fr [134.59.100.13]) by smtps-n.oca.eu (Postfix) with ESMTPSA id 107DE80527 for ; Fri, 17 Mar 2017 12:38:41 +0100 (CET) From: Damien MATTEI To: kawa@sourceware.org Subject: Re: StackOverflowError in a specialized map Date: Fri, 17 Mar 2017 11:38:00 -0000 User-Agent: KMail/1.9.6 References: <201703151608.33735.Damien.Mattei@unice.fr> <201703161154.48503.Damien.Mattei@unice.fr> In-Reply-To: <201703161154.48503.Damien.Mattei@unice.fr> MIME-Version: 1.0 Content-Type: text/plain; charset="windows-1252" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Message-Id: <201703171238.40813.Damien.Mattei@unice.fr> X-IsSubscribed: yes X-SW-Source: 2017-q1/txt/msg00083.txt.bz2 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