From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 40253 invoked by alias); 26 Mar 2017 10:56:15 -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 40233 invoked by uid 89); 26 Mar 2017 10:56:13 -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, CASE, sk:abstrac, car X-HELO: mail-wr0-f172.google.com Received: from mail-wr0-f172.google.com (HELO mail-wr0-f172.google.com) (209.85.128.172) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 26 Mar 2017 10:56:04 +0000 Received: by mail-wr0-f172.google.com with SMTP id w11so6464905wrc.3 for ; Sun, 26 Mar 2017 03:56:05 -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=6cyHxHFsk3N+/VZfwzy5NNmq/PmeHLzvuYdgzRVJRBM=; b=bfajo+/o23BOY7ciqCteJkQ31Xo4/d6+PjOMMX3D3SNmO7TPIJegUeNCCNGtCyCyBM LQ+frveJyFzWEHwwi+7xV/CyphtLuFh4z/2JFRzU2tGpi2680EhPGrz6AD4rwOcHO2p0 ROA+/9c5wi1oDHdKlO5vwt0oYKedtsvJRuPG31NB3/M/luCjhZNbWbnaEpvf6EwX+WMk 1NzmMPvrkfNewdVVuwRQKKYiUESeMjf5EZFT9bMtnT7lhWfSAJLmu5WWW1GZE5Ky8+0H nTMmto3tzWuMH6L8VP+hSppKp8fBV0XGzzJYV1DmJDHbV+wZ/v8XLEdaCJ7g7vtGPZi1 nkjQ== X-Gm-Message-State: AFeK/H1FWLGPR8dcsA60V9X3fqoWMNjtbohJNwj3a/P1wXs1NbTIN3Yb7aAXHE6j1m+4OrZhKy9Pj8cKZnPegg== X-Received: by 10.223.154.11 with SMTP id z11mr15529194wrb.76.1490525763145; Sun, 26 Mar 2017 03:56:03 -0700 (PDT) MIME-Version: 1.0 Received: by 10.223.175.45 with HTTP; Sun, 26 Mar 2017 03:55:42 -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 10:56: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/msg00096.txt.bz2 i wrote something wrong, there is a way to do it in scheme without _reverse_ and _apply_ ,here it is: ;; map-nil-iter-optim-tail-calls-fast : 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-fast + '() '((1 2 3) (4 5 6))) -> '(9 7 5) ;; (map-nil-iter-optim-tail-calls-fast (lambda (a b) (if (= a 2) '() (+ a b))) '() '((1 2 3) (4 5 6))) -> '(9 5) (define map-nil-iter-optim-tail-calls-fast (lambda (function 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) '() (let ((funct-result (apply function (map car lists)))) (if (null? funct-result) (map-nil-iter-optim-tail-calls-fast function (map cdr lists)) (cons funct-result (map-nil-iter-optim-tail-calls-fast function (map cdr lists))))))))) ;; (map-nil-iter-optim-tail-calls-fast-call + '(1 2 3) '(4 5 6)) -> '(5 7 9) ;; (map-nil-iter-optim-tail-calls-fast-call (lambda (a b) (if (= a 2) '() (+ a b))) '(1 2 3) '(4 5 6)) -> '(5 9) (define map-nil-iter-optim-tail-calls-fast-call (lambda (function list1 . more-lists) (apply map-nil-iter-optim-tail-calls-fast function (list (cons list1 more-lists))))) but unfortunately i have no more tailcalls optimisation with Kawa,even with the option (unless the option does not works at REPL but only in compiled code,will test it monday...) : albedo-2:Jkawa mattei$ kawa --full-tailcalls #|kawa:1|# (require 'regex) #|kawa:2|# (include-relative "../git/LOGIKI/lib/first-and-rest.scm") #|kawa:3|# (include-relative "../git/LOGIKI/lib/syntactic-sugar.scm") #|kawa:4|# (include-relative "../git/LOGIKI/lib/display.scm") #|kawa:5|# (include-relative "../git/LOGIKI/lib/case.scm") ;; for CASE with STRINGS #|kawa:6|# (include-relative "../git/LOGIKI/lib/list.scm") ;; for remove-last used by map.scm #|kawa:7|# (include-relative "../git/LOGIKI/lib/map.scm") ;; for map-nil* #|kawa:8|# (define wds-url "http://ad.usno.navy.mil/wds/Webtextfiles/wdsnewref.txt") #|kawa:9|# (define wds-data-str &<{&[wds-url]}) ;; could take a few seconds to GET file #|kawa:10|# (define wds-data-str-split (regex-split (string #\linefeed) wds-data-str)) #|kawa:11|# (length wds-data-str-split) 22569 #|kawa:12|# (define test (map-nil-iter-optim-tail-calls-fast-call (lambda (x) x) wds-data-str-split)) Exception in thread "main" java.lang.StackOverflowError at gnu.lists.SeqPosition.(SeqPosition.java:45) at gnu.lists.ExtPosition.(ExtPosition.java:12) at gnu.lists.LListPosition.(LListPosition.java:44) at gnu.lists.LList.getIterator(LList.java:100) at gnu.lists.AbstractSequence.getIterator(AbstractSequence.java:195) at gnu.lists.AbstractSequence.iterator(AbstractSequence.java:210) at gnu.lists.Sequences.getIterator(Sequences.java:94) at atInteractiveLevel-7.lambda14$X(stdin:10569) at atInteractiveLevel-7.apply(stdin:10550) at gnu.mapping.CallContext.runUntilDone(CallContext.java:227) at gnu.mapping.CallContext.runUntilValue(CallContext.java:303) at gnu.expr.ModuleMethodWithContext.applyN(ModuleMethodWithContext.java:63) at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141) at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48) at atInteractiveLevel-7.lambda14$X(stdin:10579) at atInteractiveLevel-7.apply(stdin:10550) at gnu.mapping.CallContext.runUntilDone(CallContext.java:227) at gnu.mapping.CallContext.runUntilValue(CallContext.java:303) at gnu.expr.ModuleMethodWithContext.applyN(ModuleMethodWithContext.java:63) at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141) at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48) at atInteractiveLevel-7.lambda14$X(stdin:10579) at atInteractiveLevel-7.apply(stdin:10550) at gnu.mapping.CallContext.runUntilDone(CallContext.java:227) at gnu.mapping.CallContext.runUntilValue(CallContext.java:303) at gnu.expr.ModuleMethodWithContext.applyN(ModuleMethodWithContext.java:63) at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141) at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48) at atInteractiveLevel-7.lambda14$X(stdin:10579) at atInteractiveLevel-7.apply(stdin:10550) at gnu.mapping.CallContext.runUntilDone(CallContext.java:227) at gnu.mapping.CallContext.runUntilValue(CallContext.java:303) at gnu.expr.ModuleMethodWithContext.applyN(ModuleMethodWithContext.java:63) at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141) at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48) at atInteractiveLevel-7.lambda14$X(stdin:10579) at atInteractiveLevel-7.apply(stdin:10550) at gnu.mapping.CallContext.runUntilDone(CallContext.java:227) at gnu.mapping.CallContext.runUntilValue(CallContext.java:303) at gnu.expr.ModuleMethodWithContext.applyN(ModuleMethodWithContext.java:63) at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141) at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48) at atInteractiveLevel-7.lambda14$X(stdin:10579) at atInteractiveLevel-7.apply(stdin:10550) at gnu.mapping.CallContext.runUntilDone(CallContext.java:227) at gnu.mapping.CallContext.runUntilValue(CallContext.java:303) at gnu.expr.ModuleMethodWithContext.applyN(ModuleMethodWithContext.java:63) at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141) at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48) at atInteractiveLevel-7.lambda14$X(stdin:10579) at atInteractiveLevel-7.apply(stdin:10550) at gnu.mapping.CallContext.runUntilDone(CallContext.java:227) at gnu.mapping.CallContext.runUntilValue(CallContext.java:303) at gnu.expr.ModuleMethodWithContext.applyN(ModuleMethodWithContext.java:63) at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141) at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48) at atInteractiveLevel-7.lambda14$X(stdin:10579) at atInteractiveLevel-7.apply(stdin:10550) at gnu.mapping.CallContext.runUntilDone(CallContext.java:227) at gnu.mapping.CallContext.runUntilValue(CallContext.java:303) at gnu.expr.ModuleMethodWithContext.applyN(ModuleMethodWithContext.java:63) at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141) at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48) at atInteractiveLevel-7.lambda14$X(stdin:10579) at atInteractiveLevel-7.apply(stdin:10550) at gnu.mapping.CallContext.runUntilDone(CallContext.java:227) at gnu.mapping.CallContext.runUntilValue(CallContext.java:303) at gnu.expr.ModuleMethodWithContext.applyN(ModuleMethodWithContext.java:63) at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141) at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48) at atInteractiveLevel-7.lambda14$X(stdin:10579) at atInteractiveLevel-7.apply(stdin:10550) at gnu.mapping.CallContext.runUntilDone(CallContext.java:227) at gnu.mapping.CallContext.runUntilValue(CallContext.java:303) at gnu.expr.ModuleMethodWithContext.applyN(ModuleMethodWithContext.java:63) at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141) at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48) at atInteractiveLevel-7.lambda14$X(stdin:10579) at atInteractiveLevel-7.apply(stdin:10550) at gnu.mapping.CallContext.runUntilDone(CallContext.java:227) at gnu.mapping.CallContext.runUntilValue(CallContext.java:303) at gnu.expr.ModuleMethodWithContext.applyN(ModuleMethodWithContext.java:63) at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141) at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48) at atInteractiveLevel-7.lambda14$X(stdin:10579) at atInteractiveLevel-7.apply(stdin:10550) On Sun, Mar 26, 2017 at 11:54 AM, Damien Mattei wrote: > 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 >>> >>>