* 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-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-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 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
* 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
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).