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 10:56:00 -0000 [thread overview]
Message-ID: <CADEOadcx=9reL+9yz5nQh3dhHEeD7AMtiUq7rgOenN7O3BiwbA@mail.gmail.com> (raw)
In-Reply-To: <CADEOadd22yGrA7GP4EFGASjDWxz3fBYaMtiL2-RRb0hM51nCFw@mail.gmail.com>
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.<init>(SeqPosition.java:45)
at gnu.lists.ExtPosition.<init>(ExtPosition.java:12)
at gnu.lists.LListPosition.<init>(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 <damien.mattei@gmail.com> 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 <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 10:56 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 [this message]
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='CADEOadcx=9reL+9yz5nQh3dhHEeD7AMtiUq7rgOenN7O3BiwbA@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).