From: Damien Mattei <damien.mattei@gmail.com>
To: Sudarshan S Chawathe <chaw@eip10.org>
Cc: Damien MATTEI <Damien.Mattei@unice.fr>,
Kawa <kawa@sourceware.org>,
jean-paul.roy@unice.fr
Subject: Re: StackOverflowError in a specialized map
Date: Sun, 26 Mar 2017 09:55:00 -0000 [thread overview]
Message-ID: <CADEOadd22yGrA7GP4EFGASjDWxz3fBYaMtiL2-RRb0hM51nCFw@mail.gmail.com> (raw)
In-Reply-To: <CADEOadeTosjSe_zCH_Lexk67LARr2mxoh5Dg8U2zKurXbPiq8w@mail.gmail.com>
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 <damien.mattei@gmail.com> 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 <chaw@eip10.org> wrote:
>>> From: Damien MATTEI <Damien.Mattei@unice.fr>
>>> 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
>>
>>
next prev parent reply other threads:[~2017-03-26 9:55 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-03-15 15:08 Damien MATTEI
2017-03-15 16:23 ` Per Bothner
2017-03-16 10:54 ` Damien MATTEI
2017-03-17 11:38 ` Damien MATTEI
2017-03-17 14:07 ` Sudarshan S Chawathe
2017-03-21 14:01 ` Damien MATTEI
2017-03-21 15:47 ` Per Bothner
2017-03-25 22:56 ` Sudarshan S Chawathe
2017-03-26 9:49 ` Damien Mattei
2017-03-26 9:55 ` Damien Mattei [this message]
2017-03-26 10:56 ` Damien Mattei
2017-03-28 8:42 ` Damien MATTEI
2017-03-28 14:21 ` Damien MATTEI
2017-03-17 10:37 ` Damien MATTEI
2017-03-17 16:00 ` Per Bothner
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CADEOadd22yGrA7GP4EFGASjDWxz3fBYaMtiL2-RRb0hM51nCFw@mail.gmail.com \
--to=damien.mattei@gmail.com \
--cc=Damien.Mattei@unice.fr \
--cc=chaw@eip10.org \
--cc=jean-paul.roy@unice.fr \
--cc=kawa@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).