From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 129869 invoked by alias); 17 Mar 2017 14:07:08 -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 129852 invoked by uid 89); 17 Mar 2017 14:07:07 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=4.1 required=5.0 tests=BAYES_00,FOREIGN_BODY1,RCVD_IN_DNSWL_NONE autolearn=no version=3.3.2 spammy=avez, vous, UNS, H*UA:GNU X-HELO: homiemail-a11.g.dreamhost.com Received: from sub3.mail.dreamhost.com (HELO homiemail-a11.g.dreamhost.com) (69.163.253.7) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 17 Mar 2017 14:07:05 +0000 Received: from homiemail-a11.g.dreamhost.com (localhost [127.0.0.1]) by homiemail-a11.g.dreamhost.com (Postfix) with ESMTP id E7E7B314C069; Fri, 17 Mar 2017 07:07:04 -0700 (PDT) Received: from vereq.eip10.org (cpe-76-179-171-141.maine.res.rr.com [76.179.171.141]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) (Authenticated sender: chaw@eip10.org) by homiemail-a11.g.dreamhost.com (Postfix) with ESMTPSA id C2EF2314C066; Fri, 17 Mar 2017 07:07:04 -0700 (PDT) Received: from chaw by vereq.eip10.org with local (Exim 4.84_2) (envelope-from ) id 1cosX1-00060E-Pe; Fri, 17 Mar 2017 10:07:03 -0400 To: Damien MATTEI cc: kawa@sourceware.org Subject: Re: StackOverflowError in a specialized map From: "Sudarshan S Chawathe" Reply-To: "Sudarshan S Chawathe" In-reply-to: Your message of "Fri, 17 Mar 2017 12:38:40 +0100." <201703171238.40813.Damien.Mattei@unice.fr> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-ID: <23076.1489759623.1@vereq.eip10.org> Date: Fri, 17 Mar 2017 14:07:00 -0000 Message-ID: <23077.1489759623@vereq.eip10.org> X-IsSubscribed: yes X-SW-Source: 2017-q1/txt/msg00084.txt.bz2 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. 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. (import (srfi 1)) (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))))))) ;; a few tests (map/remove-nulls + '(1 2 3) '(4 5 6)) (map/remove-nulls (lambda (a b) (if (= a 2) '() (+ a b))) '(1 2 3) '(4 5 6)) (length (map/remove-nulls (lambda (i j) (if (even? i) '() j)) (iota (expt 10 6)) (iota (expt 10 7)))) Regards, -chaw > From: Damien MATTEI > To: kawa@sourceware.org > Subject: Re: StackOverflowError in a specialized map > Date: Fri, 17 Mar 2017 12:38:40 +0100 > > 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 >