* StackOverflowError in a specialized map
@ 2017-03-15 15:08 Damien MATTEI
2017-03-15 16:23 ` Per Bothner
0 siblings, 1 reply; 15+ messages in thread
From: Damien MATTEI @ 2017-03-15 15:08 UTC (permalink / raw)
To: Kawa mailing list
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),
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,
the error appears both in a Tomcat web app and at REPL:
#|kawa:1|# (require 'regex)
#|kawa:2|# (include-relative "../git/LOGIKI/lib/syntactic-sugar.scm")
#|kawa:3|# (include-relative "../git/LOGIKI/lib/display.scm")
#|kawa:4|# (include-relative "../git/LOGIKI/lib/case.scm") ;; for CASE with STRINGS
#|kawa:5|# (include-relative "../git/LOGIKI/lib/map.scm") ;; for map-nil
/home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/map.scm:128:12: warning - no declaration seen for remove-last
/home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/map.scm:128:30: warning - no declaration seen for rest
#|kawa:6|# (include-relative "../git/LOGIKI/lib/list.scm") ;; for remove-last used by map.scm
/home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/list.scm:14:10: warning - no declaration seen for rest
/home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/list.scm:17:32: warning - no declaration seen for rest
/home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/list.scm:28:22: warning - no declaration seen for first
/home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/list.scm:29:17: warning - no declaration seen for first
/home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/list.scm:29:51: warning - no declaration seen for rest
/home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/list.scm:35:25: warning - no declaration seen for first
/home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/list.scm:35:56: warning - no declaration seen for rest
/home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/list.scm:39:27: warning - no declaration seen for rest
/home/mattei/Dropbox/Jkawa/../git/LOGIKI/lib/list.scm:62:12: warning - no declaration seen for rest
#|kawa:7|# (include-relative "../git/LOGIKI/lib/first-and-rest.scm")
#|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)
22527
#|kawa:12|# (define test1 (map (lambda (x) x) wds-data-str-split)
#|(---:13|# )
#|kawa:14|# (length test1)
22527
#|kawa:15|# (define test2 (map-nil (lambda (x) x) wds-data-str-split))
Exception in thread "main" java.lang.StackOverflowError
at kawa.lib.lists.isNull(lists.scm:21)
at kawa.lib.lists.apply1(lists.scm:20)
at gnu.expr.ModuleBody.applyN(ModuleBody.java:243)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.mapping.ProcedureN.apply2(ProcedureN.java:39)
at atInteractiveLevel-5.lambda7$V(stdin:10384)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
at gnu.expr.ModuleMethod.applyN(ModuleMethod.java:237)
at gnu.kawa.functions.ApplyToArgs.applyN(ApplyToArgs.java:141)
at gnu.kawa.functions.Apply.applyN(Apply.java:74)
at gnu.mapping.ProcedureN.apply3(ProcedureN.java:48)
at atInteractiveLevel-5.lambda7$V(stdin:10396)
at atInteractiveLevel-5.applyN(stdin:10379)
....
i think the 22527 elements list is too much for some recursion i use in my recursive functions (map-nil),
i'm a bit disappointed about scheme today, i thought my code was robust,but seems not...
it works with the original map ,i'm wondering how map is implemented ? i like coding in a recursive way , should i rewrite this with some iteration?
Regards,
Damien
--
Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS
^ permalink raw reply [flat|nested] 15+ messages in thread* Re: StackOverflowError in a specialized map 2017-03-15 15:08 StackOverflowError in a specialized map Damien MATTEI @ 2017-03-15 16:23 ` Per Bothner 2017-03-16 10:54 ` Damien MATTEI 2017-03-17 10:37 ` Damien MATTEI 0 siblings, 2 replies; 15+ messages in thread From: Per Bothner @ 2017-03-15 16:23 UTC (permalink / raw) To: Damien MATTEI, Kawa mailing list 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.) -- --Per Bothner per@bothner.com http://per.bothner.com/ ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 2017-03-15 16:23 ` Per Bothner @ 2017-03-16 10:54 ` Damien MATTEI 2017-03-17 11:38 ` Damien MATTEI 2017-03-17 10:37 ` Damien MATTEI 1 sibling, 1 reply; 15+ messages in thread From: Damien MATTEI @ 2017-03-16 10:54 UTC (permalink / raw) To: Kawa mailing list 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.... 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 ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 2017-03-16 10:54 ` Damien MATTEI @ 2017-03-17 11:38 ` Damien MATTEI 2017-03-17 14:07 ` Sudarshan S Chawathe 0 siblings, 1 reply; 15+ messages in thread From: Damien MATTEI @ 2017-03-17 11:38 UTC (permalink / raw) To: kawa 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 ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 2017-03-17 11:38 ` Damien MATTEI @ 2017-03-17 14:07 ` Sudarshan S Chawathe 2017-03-21 14:01 ` Damien MATTEI 0 siblings, 1 reply; 15+ messages in thread From: Sudarshan S Chawathe @ 2017-03-17 14:07 UTC (permalink / raw) To: Damien MATTEI; +Cc: kawa I wrote the following, which seems to work as desired (if I understand the original motivation correctly) and seems simpler and more idiomatic to me. It also avoids the use of 'append', which would lead to quadratic running time. It also does not need the --full-tailcalls option to Kawa (which figures out the simple case of tail call used). It uses SRFI 1 for the 'any' procedure, but that dependency is easy to remove if desired. (import (srfi 1)) (define (map/remove-nulls proc . lsts) (let loop ((lsts lsts) (result '())) (if (any null? lsts) (reverse result) (loop (map cdr lsts) (let ((proc-result (apply proc (map car lsts)))) (if (null? proc-result) result (cons proc-result result))))))) ;; a few tests (map/remove-nulls + '(1 2 3) '(4 5 6)) (map/remove-nulls (lambda (a b) (if (= a 2) '() (+ a b))) '(1 2 3) '(4 5 6)) (length (map/remove-nulls (lambda (i j) (if (even? i) '() j)) (iota (expt 10 6)) (iota (expt 10 7)))) Regards, -chaw > From: Damien MATTEI <Damien.Mattei@unice.fr> > To: kawa@sourceware.org > Subject: Re: StackOverflowError in a specialized map > Date: Fri, 17 Mar 2017 12:38:40 +0100 > > this and only this version works and WITH --full-tailcalls: > > Le Thursday 16 March 2017 11:54:48 Damien MATTEI, vous avez =E9crit=A0: > > really hard to solve, in a recursive way.... > >=20 > > i have rewrite the function with as much possible of tail recursion but = > it fails again: > >=20 > > ;; 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 (=3D a 2) '() (+ a b))) '() '(1 2 3) '= > (4 5 6)) -> '(5 9) > > (define map-nil-iter > >=20=20=20 > > (lambda (function result list1 . more-lists) > >=20 > > (letrec ((some? > > (lambda (fct list) > > ;; returns #t if (function x) returns #t for=20 > > ;; some x in the list > > (and (pair? list) > > (or > > (fct (car list)) > > (some? fct (cdr list))))))) > >=20 > >=20=20=20=20=20=20=20 > > ;; 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))))))))) > >=20 > >=20 > > ;; (map-nil-iter-call + '(1 2 3) '(4 5 6)) -> '(5 7 9) > > ;; (map-nil-iter-call (lambda (a b) (if (=3D 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)))) > >=20 > > the recursive call of map-nil-iter are no more encapsuled > >=20 > > have not try the --full-tailcalls options, will do it later.... > > tested and it works=20 > > 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 it= > erative 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 year= > s ago ... > > hope it will works with other scheme too, seems in Scheme norm to transform= > tail call in iterations automatically when possible. > damien > >=20 > > Damien > >=20 > >=20 > > Le Wednesday 15 March 2017 17:22:50 Per Bothner, vous avez =E9crit=A0: > > > 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 create= > s a java StackOverflowError on a big list (22527 elements), > > >=20 > > > Not unexpected - you're recursing on a big list. > > >=20 > > > > 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, > > >=20 > > > Try compiling map-nil with --full-tailcalls. That might do it. > > >=20 > > > However, if the stack overflow is in the final apply, that won't be eno= > ugh, > > > because that apply is not a tail-call (because of the cons of the resul= > t). > > >=20 > > > You can also try replacing: > > >=20=20=20=20=20 > > > (apply map-nil function (map XXX)) > > >=20 > > > by splice-notation: > > >=20 > > > (map-nil function @(map XXX)) > > >=20 > > > However, I don't think that would be enough for Kawa to be able to inli= > ne the tailcalls. > > > That would require the splice argument to match up with the more-lists = > rest argument, > > > which it doesn't. > > >=20 > > > If you don't mind using set-cdr! that would be a relatively simple and = > efficient solution: > > >=20 > > > (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)))) > > >=20 > > > Instead of using map, put the above snippet inside a for-each. > > >=20 > > > (The list1 parameter seems strange, as it isn't used, as far as i can t= > ell.) > >=20 > >=20 > >=20 > > > > --=20 > Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS > ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 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 0 siblings, 2 replies; 15+ messages in thread From: Damien MATTEI @ 2017-03-21 14:01 UTC (permalink / raw) To: kawa, Sudarshan S Chawathe yes, thank you, but i try to stay in a functional programming style and avoid "loop" that make code unreadable and hard to debug, i agree that append should be forbide too as it is require to explore the whole list to append a list at the tail at each new element, so i rewrite it with "cons" , and i have then only a single reverse on the whole list : ;; map-nil-iter-optim : 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 + '() '(1 2 3) '(4 5 6)) -> '(5 7 9) ;; (map-nil-iter-optim (lambda (a b) (if (= a 2) '() (+ a b))) '() '(1 2 3) '(4 5 6)) -> '(5 9) (define map-nil-iter-optim (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-optim function result (map cdr lists)) (apply map-nil-iter-optim function (cons funct-result result) ;; cons now create a reversed result list (map cdr lists))))))))) ;; (map-nil-iter-optim-call + '(1 2 3) '(4 5 6)) -> '(5 7 9) ;; (map-nil-iter-optim-call (lambda (a b) (if (= a 2) '() (+ a b))) '(1 2 3) '(4 5 6)) -> '(5 9) (define map-nil-iter-optim-call (lambda (function list1 . more-lists) (reverse ;; cons had created a reversed result list (apply map-nil-iter-optim function '() (cons list1 more-lists))))) i'm still searching a fastest way to do that... perheaps some funfamental routines as map* should be written with set-cdr! and loops and never touch them again.... and build functional programming on top of those low level routines... i do not know. Damien Le Friday 17 March 2017 15:07:03 Sudarshan S Chawathe, vous avez écrit : > I wrote the following, which seems to work as desired (if I understand > the original motivation correctly) and seems simpler and more idiomatic > to me. > > It also avoids the use of 'append', which would lead to quadratic > running time. It also does not need the --full-tailcalls option to Kawa > (which figures out the simple case of tail call used). It uses SRFI 1 > for the 'any' procedure, but that dependency is easy to remove if > desired. > > (import (srfi 1)) > > (define (map/remove-nulls proc . lsts) > (let loop ((lsts lsts) > (result '())) > (if (any null? lsts) > (reverse result) > (loop (map cdr lsts) > (let ((proc-result (apply proc > (map car lsts)))) > (if (null? proc-result) > result > (cons proc-result > result))))))) > > ;; a few tests > > (map/remove-nulls + '(1 2 3) '(4 5 6)) > > (map/remove-nulls (lambda (a b) (if (= a 2) '() (+ a b))) '(1 2 3) '(4 5 6)) > > (length (map/remove-nulls (lambda (i j) > (if (even? i) > '() > j)) > (iota (expt 10 6)) > (iota (expt 10 7)))) > > Regards, > > -chaw > > > > From: Damien MATTEI <Damien.Mattei@unice.fr> > > To: kawa@sourceware.org > > Subject: Re: StackOverflowError in a specialized map > > Date: Fri, 17 Mar 2017 12:38:40 +0100 > > > > this and only this version works and WITH --full-tailcalls: > > > > Le Thursday 16 March 2017 11:54:48 Damien MATTEI, vous avez =E9crit=A0: > > > really hard to solve, in a recursive way.... > > >=20 > > > i have rewrite the function with as much possible of tail recursion but = > > it fails again: > > >=20 > > > ;; 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 (=3D a 2) '() (+ a b))) '() '(1 2 3) '= > > (4 5 6)) -> '(5 9) > > > (define map-nil-iter > > >=20=20=20 > > > (lambda (function result list1 . more-lists) > > >=20 > > > (letrec ((some? > > > (lambda (fct list) > > > ;; returns #t if (function x) returns #t for=20 > > > ;; some x in the list > > > (and (pair? list) > > > (or > > > (fct (car list)) > > > (some? fct (cdr list))))))) > > >=20 > > >=20=20=20=20=20=20=20 > > > ;; 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))))))))) > > >=20 > > >=20 > > > ;; (map-nil-iter-call + '(1 2 3) '(4 5 6)) -> '(5 7 9) > > > ;; (map-nil-iter-call (lambda (a b) (if (=3D 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)))) > > >=20 > > > the recursive call of map-nil-iter are no more encapsuled > > >=20 > > > have not try the --full-tailcalls options, will do it later.... > > > > tested and it works=20 > > > > 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 it= > > erative 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 year= > > s ago ... > > > > hope it will works with other scheme too, seems in Scheme norm to transform= > > tail call in iterations automatically when possible. > > damien > > >=20 > > > Damien > > >=20 > > >=20 > > > Le Wednesday 15 March 2017 17:22:50 Per Bothner, vous avez =E9crit=A0: > > > > 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 create= > > s a java StackOverflowError on a big list (22527 elements), > > > >=20 > > > > Not unexpected - you're recursing on a big list. > > > >=20 > > > > > 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, > > > >=20 > > > > Try compiling map-nil with --full-tailcalls. That might do it. > > > >=20 > > > > However, if the stack overflow is in the final apply, that won't be eno= > > ugh, > > > > because that apply is not a tail-call (because of the cons of the resul= > > t). > > > >=20 > > > > You can also try replacing: > > > >=20=20=20=20=20 > > > > (apply map-nil function (map XXX)) > > > >=20 > > > > by splice-notation: > > > >=20 > > > > (map-nil function @(map XXX)) > > > >=20 > > > > However, I don't think that would be enough for Kawa to be able to inli= > > ne the tailcalls. > > > > That would require the splice argument to match up with the more-lists = > > rest argument, > > > > which it doesn't. > > > >=20 > > > > If you don't mind using set-cdr! that would be a relatively simple and = > > efficient solution: > > > >=20 > > > > (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)))) > > > >=20 > > > > Instead of using map, put the above snippet inside a for-each. > > > >=20 > > > > (The list1 parameter seems strange, as it isn't used, as far as i can t= > > ell.) > > >=20 > > >=20 > > >=20 > > > > > > > > --=20 > > Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS > > > -- Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 2017-03-21 14:01 ` Damien MATTEI @ 2017-03-21 15:47 ` Per Bothner 2017-03-25 22:56 ` Sudarshan S Chawathe 1 sibling, 0 replies; 15+ messages in thread From: Per Bothner @ 2017-03-21 15:47 UTC (permalink / raw) To: Damien MATTEI, kawa, Sudarshan S Chawathe On 03/21/2017 07:00 AM, Damien MATTEI wrote: > perheaps some funfamental routines as map* should be written with set-cdr! and loops and never touch them again.... and build functional programming on top of those low level routines... Yes, I think that makes sense. Specifically, I think we should import at least 'filter' from SRFI-1 into the default Kawa environment, and optimize it like we already do for 'map' (which compiles into a loop). Some of the other SRFI-1 function might also be worth adding. The invoke branch has "scan patterns" which act like the ellipsis in syntax-rules patterns: (PAT ...) matches a list (or actually any sequence) assuming each item matches PAT. The following squares each element of a list: #|kawa:7|# (define (sq-list [x ...]) #|.....8|# [(* x x) ...]) #|kawa:9|# (sq-list [5 7 2 3]) #(25 49 4 9) Scan patterns don't support filtering, but I'm thinking an else-less 'if' might make sense: #|kawa:10|# (define (sq-list-pos [x ...]) #|.....11|# [(if (> x 0) (* x x)) ...]) ;; doesn't work! However this has not been implemented. -- --Per Bothner per@bothner.com http://per.bothner.com/ ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 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-28 8:42 ` Damien MATTEI 1 sibling, 2 replies; 15+ messages in thread From: Sudarshan S Chawathe @ 2017-03-25 22:56 UTC (permalink / raw) To: Damien MATTEI; +Cc: kawa > 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 ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 2017-03-25 22:56 ` Sudarshan S Chawathe @ 2017-03-26 9:49 ` Damien Mattei 2017-03-26 9:55 ` Damien Mattei 2017-03-28 8:42 ` Damien MATTEI 1 sibling, 1 reply; 15+ messages in thread From: Damien Mattei @ 2017-03-26 9:49 UTC (permalink / raw) To: Sudarshan S Chawathe; +Cc: Damien MATTEI, Kawa, jean-paul.roy 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 > > ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 2017-03-26 9:49 ` Damien Mattei @ 2017-03-26 9:55 ` Damien Mattei 2017-03-26 10:56 ` Damien Mattei 0 siblings, 1 reply; 15+ messages in thread From: Damien Mattei @ 2017-03-26 9:55 UTC (permalink / raw) To: Sudarshan S Chawathe; +Cc: Damien MATTEI, Kawa, jean-paul.roy 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 >> >> ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 2017-03-26 9:55 ` Damien Mattei @ 2017-03-26 10:56 ` Damien Mattei 0 siblings, 0 replies; 15+ messages in thread From: Damien Mattei @ 2017-03-26 10:56 UTC (permalink / raw) To: Sudarshan S Chawathe; +Cc: Damien MATTEI, Kawa, jean-paul.roy 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 >>> >>> ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 2017-03-25 22:56 ` Sudarshan S Chawathe 2017-03-26 9:49 ` Damien Mattei @ 2017-03-28 8:42 ` Damien MATTEI 2017-03-28 14:21 ` Damien MATTEI 1 sibling, 1 reply; 15+ messages in thread From: Damien MATTEI @ 2017-03-28 8:42 UTC (permalink / raw) To: Kawa mailing list 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 ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 2017-03-28 8:42 ` Damien MATTEI @ 2017-03-28 14:21 ` Damien MATTEI 0 siblings, 0 replies; 15+ messages in thread From: Damien MATTEI @ 2017-03-28 14:21 UTC (permalink / raw) To: kawa 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 ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 2017-03-15 16:23 ` Per Bothner 2017-03-16 10:54 ` Damien MATTEI @ 2017-03-17 10:37 ` Damien MATTEI 2017-03-17 16:00 ` Per Bothner 1 sibling, 1 reply; 15+ messages in thread From: Damien MATTEI @ 2017-03-17 10:37 UTC (permalink / raw) To: Per Bothner; +Cc: Kawa mailing list 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. no more success > > 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)) not available seems in scheme you cannot do @something only ,@something it exists only unquote-splicing > > 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.) yes it is: (let ((lists (cons list1 more-lists))) Damien -- Damien.Mattei@unice.fr, Damien.Mattei@oca.eu, UNS / OCA / CNRS ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: StackOverflowError in a specialized map 2017-03-17 10:37 ` Damien MATTEI @ 2017-03-17 16:00 ` Per Bothner 0 siblings, 0 replies; 15+ messages in thread From: Per Bothner @ 2017-03-17 16:00 UTC (permalink / raw) To: Damien MATTEI; +Cc: Kawa mailing list On 03/17/2017 03:37 AM, Damien MATTEI wrote: >> You can also try replacing: >> >> (apply map-nil function (map XXX)) >> >> by splice-notation: >> >> (map-nil function @(map XXX)) > not available seems in scheme you cannot do @something only ,@something > it exists only unquote-splicing General splicing is a Kawa extension, not available in portable Scheme. -- --Per Bothner per@bothner.com http://per.bothner.com/ ^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2017-03-28 14:21 UTC | newest] Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-03-15 15:08 StackOverflowError in a specialized map 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 2017-03-17 10:37 ` Damien MATTEI 2017-03-17 16:00 ` Per Bothner
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).