On 8/3/22 5:33 PM, Marc Nieper-Wißkirchen wrote:
>
> ---------- Forwarded message ---------
> Von: *Marc Nieper-Wißkirchen* <xxxxxx@gmail.com
> <mailto:xxxxxx@gmail.com>>
> Date: Mi., 3. Aug. 2022 um 23:19 Uhr
> Subject: Re: Make code safe for continuation capture, part the first. ·
> gambiteer/xxxxxx@2876863
> To: John Cowan <xxxxxx@ccil.org <mailto:xxxxxx@ccil.org>>
>
> Am Mi., 3. Aug. 2022 um 22:29 Uhr schrieb John Cowan <xxxxxx@ccil.org
> <mailto:xxxxxx@ccil.org>>:
>
> On Wed, Aug 3, 2022 at 11:48 AM Bradley Lucier
> <xxxxxx@math.purdue.edu <mailto:xxxxxx@math.purdue.edu>> wrote:
>
> In the example I gave previously, this can result in much greater
> temporary memory use, up to 192 times in Gambit for bit arrays
> (which
> Gambit reports as 384 times because it has a stop-and-copy garbage
> collector, so it reports both space allocated in the old heap
> and space
> that it might need in the new heap if that structure survives GC).
>
>
> Can you explain the space cost? In procedures like `vector-map` at most
> one copy is needed when `vector-map` returns so the space cost can be at
> most twice. The actual cost can be much lower, depending on the quality
> of the GC.
Each forward iteration of vector-map remembers (1) the index, (2) the
computed value of an entry with that index and (3) the address where to
return the vector result. These three words per iteration sit on the
stack. Because it's a bit more complicated to iterate through an array,
I chose to use a list (with three words per pair). I do use an extra
word to put these values in a new specialized array, to make the mapping
between multi-index and item easier.
> Don't use a parameter. Export the procedures under two different names
> (or under the same name but in two different sub-libraries). A
> parameter wouldn't make much sense here.
"A parameter wouldn't make much sense here" is not much of an argument,
because I just said, basically, "A parameter would make sense". Want to
explain further?
I'm committed to at least finishing a call/cc-friendly version of the
library, you've convinced me of that.
Perhaps someone can offer some advice. I just added a call/cc-friendly
(interval-foldl f operator identity interval)
The call/cc-unfriendly version for large dimensions is
(let* ((lower-bounds (%%interval-lower-bounds->list interval))
(upper-bounds (%%interval-upper-bounds->list interval))
(arg (map values lower-bounds)))
; copy lower-bounds
;; I'm not particularly happy with set! here because f or
operator might capture
;; the continuation and then funny things might pursue ...
;; But it seems that the only way to have this work
efficiently without the set~
;; is to have arrays with fortran-style numbering.
;; blah
(define (iterate lower-bounds-tail
upper-bounds-tail
arg-tail
result)
(let ((lower-bound (car lower-bounds-tail))
(upper-bound (car upper-bounds-tail)))
(if (null? (cdr arg-tail))
(let loop ((i lower-bound)
(result result))
(if (= i upper-bound)
result
(begin
(set-car! arg-tail i)
(loop (+ i 1)
(operator result (apply f arg))))))
(let loop ((i lower-bound)
(result result))
(if (= i upper-bound)
result
(begin
(set-car! arg-tail i)
(loop (+ i 1)
(iterate (cdr lower-bounds-tail)
(cdr upper-bounds-tail)
(cdr arg-tail)
result))))))))
(iterate lower-bounds
upper-bounds
arg
identity))
This is somewhat space friendly. The best I could come up with for a
call/cc-friendly version is:
(let ()
(define (get-next-args reversed-args
reversed-lowers
reversed-uppers)
(let ((next-index (+ (car reversed-args) 1)))
(if (< next-index (car reversed-uppers))
(cons next-index (cdr reversed-args))
(and (not (null? (cdr reversed-args)))
(let ((tail-result (get-next-args (cdr
reversed-args)
(cdr
reversed-lowers)
(cdr
reversed-uppers))))
(and tail-result
(cons (car reversed-lowers)
tail-result)))))))
(let ((reversed-lowers (reverse
(%%interval-lower-bounds->list interval)))
(reversed-uppers (reverse
(%%interval-upper-bounds->list interval))))
(let loop ((reversed-args reversed-lowers)
(result identity))
;;; There's at least one element of the interval, so we can
;;; use a do-until loop
(let ((result (operator result (apply f (reverse
reversed-args))))
(next-reversed-args (get-next-args reversed-args
reversed-lowers
reversed-uppers)))
(if next-reversed-args
(loop next-reversed-args result)
result)))))
Because we're working with row-major (C) order, where the rightmost
index moves fastest, and we can only add and remove things from the left
of the list, I have the call
(operator result (apply f (reverse reversed-args)))
If we used column-major (Fortran) order, then I wouldn't need to reverse
the computed arg list before applying f.
But if we used column-major order, then currying an array would be
somewhat counterintuitive for a Lispish programmer. On the other hand,
except for previous versions of this SRFI, I know of no other array
library that has general array-curry, so maybe it would be OK.
I decided to macrofy the code generation for small dimensions, so
straightforward loops are now used in interval-foldl up to dimension 8,
so this general code will hardly ever be used. (But it has been tested.)
Can someone offer advice on how to recode this loop without using
reversed arguments and bounds?
Brad
