1. Nested arrays
  2. ==============
  3. It would be useful to support the same set of array primitives on nested
  4. vectors/arrays (nested arrays for short) as we do on n-D arrays. Clearly some
  5. operations don't make sense if the nested array is ragged,
  6. e.g. transpose-array. Some operations already work: (tally), (from) in some
  7. cases, ply with verbs of rank -1. Ply with verbs of rank 0 seems well
  8. defined but doesn't work now. Etc.
  9. Sparse arrays
  10. =============
  11. It's simple enough to define some data types to store sparse arrays in whatever
  12. common format (say CSR). As with nested arrays, the interest is in supporting
  13. the same set of array primitives as on n-D arrays. In many cases the complexity
  14. would not be the same, but it should be up to the user to determine the
  15. cost/convenience tradeoff.
  16. Temporaries
  17. ===========
  18. As it is, ply and fold will generate many intermediate array temporaries. Some
  19. of them are easy to remove, but others may require more work. Here's a
  20. classification.
  21. 1. Function return
  22. These are temporaries returned by cell operations. Removing them requires some
  23. way to transform (op arg ...) -> result functions into (op! result arg ...)
  24. functions. It may be possible to do this automatically by having some convention
  25. on how these functions are declared. It would be harder for general functions
  26. such as (make-verb op #f #f).
  27. This also applies to the returns of fold and ply themselves. Those should
  28. actually be the first to be fixed.
  29. 2. No oshape
  30. If a verb doesn't have an oshape, it's necessary to call the cell op at least
  31. once to compute it. Maybe the default op->verb conversion should be (make-verb
  32. op '() #f) instead of (make-verb op #f #f), as an encouragement to provide
  33. oshape. Another possibility is to compute the 1st cell, allocate, and continue
  34. the loop. Then only a cell temporary is required instead of a whole array.
  35. 3. Missed loop fusion
  36. This is part of a larger problem. A ply or fold application may not be the final
  37. result of the computation, but an intermediate one, such as when reducing an
  38. outer product.
  39. Another example is when the cell op can be composed with the ply, for example
  40. some selection operators:
  41. (ply (Jv (cut from <> 0) 1) (i. 2 2)) => (from (i. 2 2) #t 0)
  42. This also shows in the following limitation of amend!. It's cheaper to do
  43. [1] (ply! (from A i ...) op B ...)
  44. than it is to do
  45. [2] (amend! A (ply op B ...) i ...)
  46. since [2] allocates a temporary for (ply op B ...) while [1] writes directly
  47. into (from A i ...). However, [1] is bad practice because depending on the
  48. values of i ..., (from A i ...) may not be a shared array over A, so the
  49. statement would not amend A in those cases. On the other hand, amend! will
  50. amend A for any valid i ... . Loop fusion should remove the temporary in [2]
  51. and allow it to be as efficient as [1] in every case.
  52. Implementations of rank above the rank of the verb
  53. ==================================================
  54. Sometimes it's convenient to implement a verb of rank-k as a function that takes
  55. arrays of higher rank. This is normally done for efficiency reasons when the
  56. function is implemented in a foreign module. For example, if a function
  57. (rotate-vector v) is implemented in C, it makes sense for the function
  58. to take a whole block of vectors at once, instead of relying on the rank
  59. extension mechanism to call it for each 1-slice in this block.
  60. The verb definition for verbs of rank k should support using lambas of rank
  61. q≥k. When the argument's rank is in [k, q], it suffices to reshape in and out of
  62. the call. When the argument's rank is >q it may not be possible to reshape
  63. without copying, depending on the strides of the argument. Therefore the
  64. argument traversal should use the lambda rank q instead of the verb rank k.