This is the mail archive of the
kawa@sourceware.org
mailing list for the Kawa project.
Re: StackOverflowError in a specialized map
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
>>>
>>>