From: Damien MATTEI <Damien.Mattei@unice.fr>
To: kawa@sourceware.org
Subject: Re: StackOverflowError in a specialized map
Date: Tue, 28 Mar 2017 14:21:00 -0000 [thread overview]
Message-ID: <201703281621.13020.Damien.Mattei@unice.fr> (raw)
In-Reply-To: <201703281042.25649.Damien.Mattei@unice.fr>
i removed the nested _let_ ,the only thing that make crash the stack are the _cons_ that grow at each recursive call
for some explanation see:
https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1
Damien
Le Tuesday 28 March 2017 10:42:25 Damien MATTEI, vous avez écrit :
> Le Saturday 25 March 2017 23:56:01 Sudarshan S Chawathe, vous avez écrit :
> > > 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
> >
> >
> >
>
> i have tested your solution (just used some? in place of any):
> ;; (map/remove-nulls-1 (lambda (a b) (if (= a 2) '() (+ a b))) '(1 2 3) '(4 5 6)) -> '(5 9)
> (define (map/remove-nulls-1 proc . lsts)
> (define (f lsts result)
> (if (some? #;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 '()))
>
> and it worked with Kawa without the need of --fulltail-calls option:
> [mattei@moita ~]$ kawa
> #|kawa:1|# (require 'regex)
> #|kawa:2|# (include-relative "../git/LOGIKI/lib/first-and-rest.scm")
> /dev/stdin:2:20: cannot open file "../git/LOGIKI/lib/first-and-rest.scm"
> #|kawa:3|# (exit)
> [mattei@moita ~]$ cd Dropbox/Jkawa/
> [mattei@moita Jkawa]$ kawa
> #|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")
> #|kawa:6|#
> #|kawa:7|# (include-relative "../git/LOGIKI/lib/list.scm")
> #|kawa:8|# (include-relative "../git/LOGIKI/lib/map.scm") ;; for map-nil*
> /home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/map.scm:671:9: warning - no declaration seen for some?
> #|kawa:9|# (include-relative "../git/LOGIKI/lib/set.scm")
> /home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/set.scm:131:3: warning - no declaration seen for andmap
> #|kawa:10|#
> #|kawa:11|# (define wds-url "http://ad.usno.navy.mil/wds/Webtextfiles/wdsnewref.txt")
> #|kawa:12|# (define wds-data-str &<{&[wds-url]})
> #|kawa:13|# (define wds-data-str-split (regex-split (string #\linefeed) wds-data-str))
> #|kawa:14|# (length wds-data-str-split)
> 22569
> #|kawa:15|# (define test (map/remove-nulls-1 (lambda (x) x) wds-data-str-split))
> #|kawa:16|# (length test)
> 22569
>
> i think what prevent the optimisation to work in Kawa was the nesting of the recursion call in a let,
> and the nesting of the tail call in a _cons_
>
> Damien
>
--
Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS
next prev parent reply other threads:[~2017-03-28 14:21 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
2017-03-26 10:56 ` Damien Mattei
2017-03-28 8:42 ` Damien MATTEI
2017-03-28 14:21 ` Damien MATTEI [this message]
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=201703281621.13020.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).