From: Damien MATTEI <Damien.Mattei@unice.fr>
To: kawa@sourceware.org
Subject: Re: StackOverflowError in a specialized map
Date: Fri, 17 Mar 2017 11:38:00 -0000 [thread overview]
Message-ID: <201703171238.40813.Damien.Mattei@unice.fr> (raw)
In-Reply-To: <201703161154.48503.Damien.Mattei@unice.fr>
this and only this version works and WITH --full-tailcalls:
Le Thursday 16 March 2017 11:54:48 Damien MATTEI, vous avez écrit :
> really hard to solve, in a recursive way....
>
> i have rewrite the function with as much possible of tail recursion but it fails again:
>
> ;; 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 (= a 2) '() (+ a b))) '() '(1 2 3) '(4 5 6)) -> '(5 9)
> (define map-nil-iter
>
> (lambda (function result list1 . more-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.
> (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)))))))))
>
>
> ;; (map-nil-iter-call + '(1 2 3) '(4 5 6)) -> '(5 7 9)
> ;; (map-nil-iter-call (lambda (a b) (if (= 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))))
>
> the recursive call of map-nil-iter are no more encapsuled
>
> have not try the --full-tailcalls options, will do it later....
tested and it works
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 iterative 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 years ago ...
hope it will works with other scheme too, seems in Scheme norm to transform tail call in iterations automatically when possible.
damien
>
> Damien
>
>
> Le Wednesday 15 March 2017 17:22:50 Per Bothner, vous avez écrit :
> > 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 creates a java StackOverflowError on a big list (22527 elements),
> >
> > Not unexpected - you're recursing on a big list.
> >
> > > 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,
> >
> > Try compiling map-nil with --full-tailcalls. That might do it.
> >
> > However, if the stack overflow is in the final apply, that won't be enough,
> > because that apply is not a tail-call (because of the cons of the result).
> >
> > You can also try replacing:
> >
> > (apply map-nil function (map XXX))
> >
> > by splice-notation:
> >
> > (map-nil function @(map XXX))
> >
> > However, I don't think that would be enough for Kawa to be able to inline the tailcalls.
> > That would require the splice argument to match up with the more-lists rest argument,
> > which it doesn't.
> >
> > If you don't mind using set-cdr! that would be a relatively simple and efficient solution:
> >
> > (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))))
> >
> > Instead of using map, put the above snippet inside a for-each.
> >
> > (The list1 parameter seems strange, as it isn't used, as far as i can tell.)
>
>
>
--
Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS
next prev parent reply other threads:[~2017-03-17 11:38 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 [this message]
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
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=201703171238.40813.Damien.Mattei@unice.fr \
--to=damien.mattei@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).