From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 100819 invoked by alias); 21 Mar 2017 14:01: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 100776 invoked by uid 89); 21 Mar 2017 14:01:03 -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, eno, figures 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; Tue, 21 Mar 2017 14:01:00 +0000 Received: from [192.168.109.88] (natoca100-13.unice.fr [134.59.100.13]) by smtps-n.oca.eu (Postfix) with ESMTPSA id C10A080128; Tue, 21 Mar 2017 15:00:57 +0100 (CET) From: Damien MATTEI To: kawa@sourceware.org, "Sudarshan S Chawathe" Subject: Re: StackOverflowError in a specialized map Date: Tue, 21 Mar 2017 14:01:00 -0000 User-Agent: KMail/1.9.6 References: <23077.1489759623@vereq.eip10.org> In-Reply-To: <23077.1489759623@vereq.eip10.org> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Message-Id: <201703211500.57497.Damien.Mattei@unice.fr> X-IsSubscribed: yes X-SW-Source: 2017-q1/txt/msg00089.txt.bz2 yes, thank you, but i try to stay in a functional programming style and avo= id "loop" that make code unreadable and hard to debug, i agree that append should be forbide too as it is require to explore the = whole list to append a list at the tail at each new element, so i rewrite it with "cons" , and i have t= hen only a single reverse=20 on the whole list : ;; map-nil-iter-optim : 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-optim + '() '(1 2 3) '(4 5 6)) -> '(5 7 9) ;; (map-nil-iter-optim (lambda (a b) (if (=3D a 2) '() (+ a b))) '() '(1 2 = 3) '(4 5 6)) -> '(5 9) (define map-nil-iter-optim =20=20 (lambda (function result list1 . more-lists) (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 ;; 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-optim function result (map cdr lists)) (apply map-nil-iter-optim function (cons funct-result result) ;; cons now create a reversed result list (map cdr lists))))))))) ;; (map-nil-iter-optim-call + '(1 2 3) '(4 5 6)) -> '(5 7 9) ;; (map-nil-iter-optim-call (lambda (a b) (if (=3D a 2) '() (+ a b))) '(1 2= 3) '(4 5 6)) -> '(5 9) (define map-nil-iter-optim-call (lambda (function list1 . more-lists) (reverse ;; cons had created a reversed result list (apply map-nil-iter-optim function '() (cons list1 more-lists))))) i'm still searching a fastest way to do that... perheaps some funfamental routines as map* should be written with set-cdr! = and loops and never touch them again.... and build functional programming o= n top of those low level routines... i do not know. Damien Le Friday 17 March 2017 15:07:03 Sudarshan S Chawathe, vous avez =E9crit=A0: > I wrote the following, which seems to work as desired (if I understand > the original motivation correctly) and seems simpler and more idiomatic > to me. >=20 > It also avoids the use of 'append', which would lead to quadratic > running time. It also does not need the --full-tailcalls option to Kawa > (which figures out the simple case of tail call used). It uses SRFI 1 > for the 'any' procedure, but that dependency is easy to remove if > desired. >=20 > (import (srfi 1)) >=20 > (define (map/remove-nulls proc . lsts) > (let loop ((lsts lsts) > (result '())) > (if (any null? lsts) > (reverse result) > (loop (map cdr lsts) > (let ((proc-result (apply proc > (map car lsts)))) > (if (null? proc-result) > result > (cons proc-result > result))))))) >=20 > ;; a few tests >=20 > (map/remove-nulls + '(1 2 3) '(4 5 6)) >=20 > (map/remove-nulls (lambda (a b) (if (=3D a 2) '() (+ a b))) '(1 2 3) '(4 = 5 6)) >=20 > (length (map/remove-nulls (lambda (i j) > (if (even? i) > '() > j)) > (iota (expt 10 6)) > (iota (expt 10 7)))) >=20 > Regards, >=20 > -chaw >=20 >=20 > > From: Damien MATTEI > > To: kawa@sourceware.org > > Subject: Re: StackOverflowError in a specialized map > > Date: Fri, 17 Mar 2017 12:38:40 +0100 > >=20 > > this and only this version works and WITH --full-tailcalls: > >=20 > > Le Thursday 16 March 2017 11:54:48 Damien MATTEI, vous avez =3DE9crit= =3DA0: > > > really hard to solve, in a recursive way.... > > >=3D20 > > > i have rewrite the function with as much possible of tail recursion = but =3D > > it fails again: > > >=3D20 > > > ;; map-nil-iter : a map version that exclude nil results > > > ;; the same as map-with-lambdas but will exclude from the result list= the=3D > > '() result of function > > > ;; > > > ;; (map-nil-iter + '() '(1 2 3) '(4 5 6)) -> '(5 7 9) > > > ;; (map-nil-iter (lambda (a b) (if (=3D3D a 2) '() (+ a b))) '() '(1 = 2 3) '=3D > > (4 5 6)) -> '(5 9) > > > (define map-nil-iter > > >=3D20=3D20=3D20 > > > (lambda (function result list1 . more-lists) > > >=3D20 > > > (letrec ((some? > > > (lambda (fct list) > > > ;; returns #t if (function x) returns #t for=3D20 > > > ;; some x in the list > > > (and (pair? list) > > > (or > > > (fct (car list)) > > > (some? fct (cdr list))))))) > > >=3D20 > > >=3D20=3D20=3D20=3D20=3D20=3D20=3D20 > > > ;; 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))))))))) > > >=3D20 > > >=3D20 > > > ;; (map-nil-iter-call + '(1 2 3) '(4 5 6)) -> '(5 7 9) > > > ;; (map-nil-iter-call (lambda (a b) (if (=3D3D a 2) '() (+ a b))) '(1= 2 3) =3D > > '(4 5 6)) -> '(5 9) > > > (define map-nil-iter-call > > > (lambda (function list1 . more-lists) > > > (apply map-nil-iter function '() (cons list1 more-lists)))) > > >=3D20 > > > the recursive call of map-nil-iter are no more encapsuled > > >=3D20 > > > have not try the --full-tailcalls options, will do it later.... > >=20 > > tested and it works=3D20 > >=20 > > great! > >=20 > > got the idea from university course and i reread the chapter at page 27= of =3D > > second edition of > > SICP Structure and Interpretation of Computer Program (Abelson adn Sus= sman=3D > > )about tail recursion .... explaining how to transform a recursion in a= n it=3D > > erative form using an accumulator to pass result on the factorial examp= le... > > perhaps the first time i really read this strange old book i bought 25 = year=3D > > s ago ... > >=20 > > hope it will works with other scheme too, seems in Scheme norm to trans= form=3D > > tail call in iterations automatically when possible. > > damien > > >=3D20 > > > Damien > > >=3D20 > > >=3D20 > > > Le Wednesday 15 March 2017 17:22:50 Per Bothner, vous avez =3DE9crit= =3DA0: > > > > On 03/15/2017 08:08 AM, Damien MATTEI wrote: > > > > > Hello, > > > > > > > > > > i have a custom definition of map ( https://github.com/damien-mat= tei/=3D > > 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=3D > > 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 cr= eate=3D > > s a java StackOverflowError on a big list (22527 elements), > > > >=3D20 > > > > Not unexpected - you're recursing on a big list. > > > >=3D20 > > > > > 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, > > > >=3D20 > > > > Try compiling map-nil with --full-tailcalls. That might do it. > > > >=3D20 > > > > However, if the stack overflow is in the final apply, that won't be= eno=3D > > ugh, > > > > because that apply is not a tail-call (because of the cons of the r= esul=3D > > t). > > > >=3D20 > > > > You can also try replacing: > > > >=3D20=3D20=3D20=3D20=3D20 > > > > (apply map-nil function (map XXX)) > > > >=3D20 > > > > by splice-notation: > > > >=3D20 > > > > (map-nil function @(map XXX)) > > > >=3D20 > > > > However, I don't think that would be enough for Kawa to be able to = inli=3D > > ne the tailcalls. > > > > That would require the splice argument to match up with the more-li= sts =3D > > rest argument, > > > > which it doesn't. > > > >=3D20 > > > > If you don't mind using set-cdr! that would be a relatively simple = and =3D > > efficient solution: > > > >=3D20 > > > > (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)))) > > > >=3D20 > > > > Instead of using map, put the above snippet inside a for-each. > > > >=3D20 > > > > (The list1 parameter seems strange, as it isn't used, as far as i c= an t=3D > > ell.) > > >=3D20 > > >=3D20 > > >=3D20 > >=20 > >=20 > >=20 > > --=3D20 > > Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS > >=20 >=20 --=20 Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS