From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21694 invoked by alias); 26 Mar 2017 09:55:05 -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 21584 invoked by uid 89); 26 Mar 2017 09:55:04 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.3 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM,SPF_PASS autolearn=no version=3.3.2 spammy=monday, car X-HELO: mail-wr0-f176.google.com Received: from mail-wr0-f176.google.com (HELO mail-wr0-f176.google.com) (209.85.128.176) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 26 Mar 2017 09:55:02 +0000 Received: by mail-wr0-f176.google.com with SMTP id w11so5400309wrc.3 for ; Sun, 26 Mar 2017 02:55:02 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=XGT1Jqs8vGKP9IVtY01dJm5xB4UYMtpWto5xlXIQ8Io=; b=BXeosaVu+8yWNAwwuUiAdMtC4WSGBFI4FZhwF5UChXTKFh1+olacB5fn0kKkiqRb7v 6HO6ojVH0x4oIfhyVJOgWsuOjhcKQY1pSAoGNM6V+GPRi64xw9Zh3DSRaCq/g3vXAxyZ PMhjJEDmPealGnUFslGJFV/BR5ttSY6jkxd4ci7EBpvL31E+itx7ThVzmYAaDLSr34GT tGz8O2nHzeSr/MtGSRKmjxtkhhnhXCX48heCB8Uffngu/zi2bvUQ/DFpEVmsvLm6+Lms 9Yx7WInZKFC/yu/bK+mL+CgCxfZ/DT41d464ySSxsdyWTfIX0X2OS8xRRGteQ0QNlNI/ MO9Q== X-Gm-Message-State: AFeK/H0kTi/6HSlDHHC7GwDAh0vLRIXz6E+OuP07ZHwS66HhhMf24D914T7V5X4rkSGTQkrCwL2zABjVp4CNwQ== X-Received: by 10.28.209.202 with SMTP id i193mr5061835wmg.17.1490522100971; Sun, 26 Mar 2017 02:55:00 -0700 (PDT) MIME-Version: 1.0 Received: by 10.223.175.45 with HTTP; Sun, 26 Mar 2017 02:54:40 -0700 (PDT) In-Reply-To: References: <201703211500.57497.Damien.Mattei@unice.fr> <25387.1490482561@vereq.eip10.org> From: Damien Mattei Date: Sun, 26 Mar 2017 09:55:00 -0000 Message-ID: Subject: Re: StackOverflowError in a specialized map To: Sudarshan S Chawathe Cc: Damien MATTEI , Kawa , jean-paul.roy@unice.fr Content-Type: text/plain; charset=UTF-8 X-IsSubscribed: yes X-SW-Source: 2017-q1/txt/msg00095.txt.bz2 part of the answer that did not reached the mailing list was here: https://groups.google.com/forum/#!msg/comp.lang.scheme/40wwKHG43Uw/wq71EH4nCQAJ Damien On Sun, Mar 26, 2017 at 11:49 AM, Damien Mattei wrote: > Hi Chaw, > > thank for your message, > i have posted an answer friday unfortunately it does not correctly the > mailins list due to copy-carbon i think, i have not the text of my > answer here but i will be able to repost it on monday. > > basically it works now in kawa without use of --tail-calls option, > the only penality is that i need in my solution ,as of yours to use a > _reverse_ call , > but there is nothing else to do unfortunately ,except use some > iteration and set-cdr! because in LisP and Scheme lists are "linked" > in only one way from begin to tail (end) ,and you cannot explore the > list in reverse starting from tail (end) to begin , because CAR is > pointing to element and CDR to rest of the list,when you have a PAIR > you can find the CDR but with the CDR you cannot get the previous > PAIR, so in LisP and Scheme you cannot find such a recursive function > to do this without at least at the end reversing the list. > > here is my last version: > > ;; map-nil-iter-optim-tail-calls : 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-tail-calls + '() '((1 2 3) (4 5 6))) -> '(9 7 5) > ;; (map-nil-iter-optim-tail-calls (lambda (a b) (if (= a 2) '() (+ a > b))) '() '((1 2 3) (4 5 6))) -> '(9 5) > (define map-nil-iter-optim-tail-calls > > (lambda (function result lists) > > (letrec ((some? > (lambda (fct list) > ;; returns #t 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. > > (if (some? null? lists) > > result > > (let* ((funct-result (apply function (map car lists)))) > > (if (null? funct-result) > > (map-nil-iter-optim-tail-calls function result (map cdr lists)) > > (map-nil-iter-optim-tail-calls > function > (cons funct-result result) ;; cons now create a reversed result list > (map cdr lists)))))))) > > > ;; (map-nil-iter-optim-tail-calls-call + '(1 2 3) '(4 5 6)) -> '(5 7 9) > ;; (map-nil-iter-optim-tail-calls-call (lambda (a b) (if (= a 2) '() > (+ a b))) '(1 2 3) '(4 5 6)) -> '(5 9) > (define map-nil-iter-optim-tail-calls-call > (lambda (function list1 . more-lists) > (reverse ;; cons had created a reversed result list > (apply map-nil-iter-optim-tail-calls > function > '() > (list > (cons list1 more-lists)))))) > > > regards, > > Damien > > On Sat, Mar 25, 2017 at 11:56 PM, Sudarshan S Chawathe wrote: >>> From: Damien MATTEI >>> Date: Tue, 21 Mar 2017 15:00:57 +0100 >>> >>> 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 suspect I may be misunderstanding your quest, but I don't see a >> significant difference between a 'named let' and a nested function >> definition (with respect to being functional programming). Perhaps I >> should have used a name 'recur' instead of 'loop' in my earlier version. >> >> For example, if we wish to avoid named let altogether for some reason, >> we could use the following variant of my earlier implementation. >> >> (define (map/remove-nulls-1 proc . lsts) >> (define (f lsts result) >> (if (any null? lsts) >> (reverse result) >> (f (map cdr lsts) >> (let ((proc-result (apply proc >> (map car lsts)))) >> (if (null? proc-result) >> result >> (cons proc-result >> result)))))) >> (f lsts '())) >> >> Or, going another way, we could use fold: >> >> (define (map/remove-nulls-2 proc . lsts) >> (reverse (apply fold >> (lambda fargs >> (let ((accum (last fargs)) >> (pargs (drop-right fargs 1))) >> (let ((r (apply proc pargs))) >> (if (null? r) >> accum >> (cons r accum))))) >> '() >> lsts))) >> >> As before, I'm using some SRFI 1 procedures for convenience; they can be >> avoided easily: any, fold, last, drop-right. >> >> Both the above versions, like the one I posted earlier, work without >> problems in Kawa without needing the --full-tailcalls option (i.e., Kawa >> properly detects and eliminates and simple cases of tail calls they >> use). The slight awkwardness of last/drop-right is due to the >> >> But, as I noted before, perhaps I'm missing the main point of the >> original question. >> >> Regards, >> >> -chaw >> >>