Debian Codegraph @

autoray/lazy/core.py

raw
1 """Core lazy array functionality."""
2
3 import operator
4 import threading
5 import functools
6 import itertools
7 import contextlib
8 import collections
9
10 from ..autoray import (
11 shape,
12 astype,
13 get_dtype_name,
14 get_lib_fn,
15 infer_backend,
16 multi_class_priorities,
17 register_backend,
18 register_function,
19 tree_flatten,
20 tree_map,
21 tree_iter,
22 tree_unflatten,
23 )
24 from .draw import (
25 plot_graph,
26 plot_circuit,
27 plot_history_size_footprint,
28 plot_history_functions,
29 plot_history_stats,
30 )
31
32
33 _EMPTY_DICT = {}
34 get_depth = operator.attrgetter("_depth")
35 get_data = operator.attrgetter("_data")
36 get_dtype = operator.attrgetter("dtype")
37
38 # ------------------------ traversal and computation ------------------------ #
39
40
41 def is_lazy_array(x):
42 """Check if ``x`` is a lazy array."""
43 return isinstance(x, LazyArray)
44
45
46 def to_queue(lz):
47 """Parse a pytree of lazy arrays into a queue of nodes, sorted by depth.
48 This is useful for traversing the computational graph of multiple outputs
49 in topological order.
50 """
51 if isinstance(lz, LazyArray):
52 return [lz]
53 queue = tree_flatten(lz, is_lazy_array)
54 queue.sort(key=get_depth)
55 return queue
56
57
58 def descend(lz):
59 """Generate each unique computational node. Use ``ascend`` if you need to
60 visit children before parents.
61
62 Parameters
63 ----------
64 lz : pytree of LazyArray
65 The output node(s) of the computational graph to descend.
66
67 Yields
68 ------
69 LazyArray
70 """
71 queue = to_queue(lz)
72 seen = set()
73 while queue:
74 node = queue.pop()
75 nid = id(node)
76 if nid not in seen:
77 yield node
78 queue.extend(node._deps)
79 seen.add(nid)
80
81
82 def ascend(lz):
83 """Generate each unique computational node, from leaves to root. I.e. a
84 topological ordering of the computational graph. Moreover, the nodes
85 are visited 'deepest first'.
86
87 Parameters
88 ----------
89 lz : pytree of LazyArray
90 The output node(s) of the computational graph to ascend to.
91
92 Yields
93 ------
94 LazyArray
95 """
96 queue = to_queue(lz)
97 visited = set()
98
99 while queue:
100 node = queue[-1]
101 unvisited_deps = [c for c in node._deps if id(c) not in visited]
102 k = len(unvisited_deps)
103 if k == 1:
104 # single unvisited dependency, add it to the queue
105 queue.append(unvisited_deps[0])
106 elif k >= 2:
107 # sort dependencies by depth and add them to the queue
108 unvisited_deps.sort(key=get_depth)
109 queue.extend(unvisited_deps)
110 else: # k == 0:
111 # all dependencies visited, yield this node
112 queue.pop()
113 nid = id(node)
114 if nid not in visited:
115 yield node
116 visited.add(nid)
117
118
119 def compute(lz):
120 """Compute the value of one or more lazy arrays. All nodes that are
121 computed clear any references to their function, arguments and
122 dependencies, and store the result in their ``_data`` attribute.
123
124 Parameters
125 ----------
126 lz : pytree of LazyArray
127 The output node(s) of the computational graph to compute.
128
129 Returns
130 -------
131 array or tuple of array
132 The computed value(s) of the lazy array(s).
133 """
134 for node in ascend(lz):
135 node._materialize()
136 return tree_map(get_data, lz, is_lazy_array)
137
138
139 def compute_constants(lz, variables):
140 """Fold constant arrays - everything not dependent on ``variables`` -
141 into the graph.
142
143 Parameters
144 ----------
145 lz : pytree of LazyArray
146 The output node(s) of the computational graph.
147 variables : pytree of LazyArray
148 Nodes that should be treated as variable. I.e. any descendants will
149 not be folded into the graph.
150 """
151 variables = set(tree_iter(variables, is_lazy_array))
152
153 # must ascend
154 for node in ascend(lz):
155 if not any(c in variables for c in node._deps):
156 # can fold
157 node._materialize()
158 else:
159 # inherit variable status
160 variables.add(node)
161
162
163 def get_source(lz, params=None):
164 """Write the source code of an unravelled version of the computational
165 graph, injecting required runtime objects into ``params``.
166
167 Parameters
168 ----------
169 lz : LazyArray or sequence of LazyArray
170 The output node(s) of the computational graph to write the source code
171 for. Their corresponding label is ``f"x{id(node)}"`` in the
172 source code.
173
174 Returns
175 -------
176 str
177 The source code of the computational graph, suitable for ``exec``.
178 """
179 if params is None:
180 # locals space mapping LazyArray names to values
181 params = {}
182
183 delete_checked = set()
184 s = [] # source code lines
185
186 for node in reversed(tuple(ascend(lz))):
187 # when *descending*, the first encounter of a node is the
188 # *last* time it is referenced in forward pass -> delete,
189 # need to do this for GC since running in single big function
190 for c in node._deps:
191 if c not in delete_checked:
192 if c._deps:
193 # is an intermediate - safe to delete. While we could
194 # delete input variables, we want to keep input *constants*
195 s.append(f"del x{id(c)}")
196 delete_checked.add(c)
197
198 if node._data is None:
199 # create the array via computation
200 s.append(node.as_string(params))
201 else:
202 # inject the already computed data as constant
203 params[f"x{id(node)}"] = node._data
204
205 # reverse (ascend) into source code
206 return "\n".join(reversed(s))
207
208
209 class Function:
210 """Get a compiled (by python ``compile``), function that performs the
211 computational graph corresponding to ``inputs`` -> ``outputs``. The
212 signature of the function is ``func(input_arrays) -> output_arrays``. As an
213 intermediate step, the computational graph is traced to a flattened source
214 code string.
215
216 Parameters
217 ----------
218 inputs : pytree of LazyArray
219 The input node(s) of the computational graph.
220 outputs : pytree of LazyArray
221 The output node(s) of the computational graph.
222 fold_constants : bool, optional
223 If True, fold constant arrays (those with no dependence on ``inputs``)
224 into the graph ahead of compile.
225
226 See Also
227 --------
228 get_source, compute
229 """
230
231 __slots__ = (
232 "_in_names",
233 "_out_names",
234 "_out_tree",
235 "_source",
236 "_code",
237 "_locals",
238 )
239
240 def __init__(self, inputs, outputs, fold_constants=True):
241 if fold_constants:
242 # compute everything not dependent on inputs
243 compute_constants(outputs, variables=inputs)
244
245 # write source and populate locals mapping that function will run
246 # under, locals will include the functions and other constant objects
247 self._locals = {}
248 self._source = get_source(outputs, params=self._locals)
249
250 # compile source
251 self._code = compile(
252 source=self._source,
253 filename="<string>",
254 mode="exec",
255 optimize=1,
256 )
257
258 # get names to inject and extract arrays into and from locals
259 self._in_names = tuple(f"x{id(v)}" for v in tree_iter(inputs))
260 outs_flat, self._out_tree = tree_flatten(outputs, get_ref=True)
261 self._out_names = tuple(f"x{id(v)}" for v in outs_flat)
262
263 def __call__(self, *args):
264 # this allows any matching zipped tree
265 for name, array in zip(self._in_names, tree_iter(args)):
266 self._locals[name] = array
267
268 # run the byte-compiled function with the updated locals
269 exec(self._code, None, self._locals)
270
271 # remove inputs from locals
272 for name in self._in_names:
273 del self._locals[name]
274
275 # pop outputs from locals
276 outs = tuple(self._locals.pop(name) for name in self._out_names)
277
278 # return the outputs in the original tree structure
279 return tree_unflatten(outs, self._out_tree)
280
281 def __getstate__(self):
282 # can't pickle the code object -> recompile in setstate
283 return (
284 self._in_names,
285 self._out_names,
286 self._out_tree,
287 self._source,
288 self._locals,
289 )
290
291 def __setstate__(self, state):
292 (
293 self._in_names,
294 self._out_names,
295 self._out_tree,
296 self._source,
297 self._locals,
298 ) = state
299
300 # recompile the source
301 self._code = compile(
302 source=self._source,
303 filename="<string>",
304 mode="exec",
305 optimize=1,
306 )
307
308 def print_source(self):
309 """Print the source code of the compiled function."""
310 print(self._source)
311
312 def __repr__(self):
313 insig = f"{len(self._in_names)} input(s)"
314 outsig = f"{len(self._out_names)} output(s) "
315 return f"<Function({insig}) -> {outsig}>"
316
317
318 # --------------------------- computational nodes --------------------------- #
319
320
321 class Placeholder:
322 """A singleton object to use as a placeholder in a LazyArray."""
323
324 __slots__ = ()
325
326 def __repr__(self):
327 return "Placeholder"
328
329
330 PLACEHOLDER = Placeholder()
331
332
333 class LazyArray:
334 """A lazy array representing a node in a computational graph.
335
336 Parameters
337 ----------
338 backend : str
339 The backend of the array were it to be computed. This can be ``None``
340 but this may cause problems when propagating information about which
341 functions to import to child nodes.
342 fn : callable
343 The function to call to compute the array, presumable imported from
344 ``backend``. This can be ``None`` if the array already has data (e.g.
345 is an input).
346 args : tuple
347 The positional arguments to pass to ``fn``, which might be
348 ``LazyArray`` instances.
349 kwargs : dict
350 The keyword arguments to pass to ``fn``, which might be
351 ``LazyArray`` instances.
352 shape : tuple
353 The shape of the array that ``fn(*args, **kwargs)`` will return, or
354 the shape of the array that ``data`` has.
355 deps : tuple, optional
356 The ``LazyArray`` instances that ``fn(*args, **kwargs)`` depends on.
357 If not specified, these will be automatically found from ``args`` and
358 ``kwargs``, specifying them manually is slightly more efficient.
359
360 """
361
362 __slots__ = (
363 "_backend",
364 "_fn",
365 "_args",
366 "_kwargs",
367 "_shape",
368 "_data",
369 "_deps",
370 "_depth",
371 )
372
373 def __init__(
374 self,
375 backend,
376 fn,
377 args,
378 kwargs,
379 shape,
380 deps=None,
381 ):
382 # info required to perform the computation
383 self._backend = backend
384 self._fn = fn
385 self._args = args
386 if kwargs is None:
387 self._kwargs = _EMPTY_DICT
388 else:
389 self._kwargs = kwargs
390
391 # resulting array information
392 self._shape = shape
393 self._data = None
394
395 # lazy arrays this ``LazyArray`` depends on
396 if deps is None:
397 # automatically find them
398 self._deps = (*find_lazy(self._args), *find_lazy(self._kwargs))
399 else:
400 # manually specified (slightly more efficient)
401 self._deps = deps
402
403 # tracking depth helps when ordering the computational graph
404 if self._deps:
405 self._depth = max(d._depth for d in self._deps) + 1
406 else:
407 self._depth = 0
408
409 @classmethod
410 def from_data(cls, data):
411 """Create a new ``LazyArray`` directly from a concrete array."""
412 obj = cls.__new__(cls)
413 obj._backend = infer_backend(data)
414 obj._fn = obj._args = obj._kwargs = None
415 obj._shape = shape(data)
416 obj._data = data
417 obj._deps = ()
418 obj._depth = 0
419 return obj
420
421 @classmethod
422 def from_shape(cls, shape, backend="numpy"):
423 """Create a new ``LazyArray`` with a given shape."""
424 obj = cls.__new__(cls)
425 obj._backend = backend
426 obj._fn = obj._args = obj._kwargs = None
427 obj._shape = tuple(map(int, shape))
428 obj._data = PLACEHOLDER
429 obj._deps = ()
430 obj._depth = 0
431 return obj
432
433 def to(
434 self,
435 fn,
436 args=None,
437 kwargs=None,
438 backend=None,
439 shape=None,
440 deps=None,
441 ):
442 """Create a new ``LazyArray``, by default propagating backend, shape,
443 and deps from the the current LazyArray.
444 """
445 return LazyArray(
446 fn=fn,
447 args=args if args is not None else (self,),
448 kwargs=kwargs,
449 backend=backend if backend is not None else self._backend,
450 shape=shape if shape is not None else self.shape,
451 deps=deps if deps is not None else (self,),
452 )
453
454 def _materialize(self):
455 """Recursively compute all required args and kwargs for this node
456 before computing itself and dereferencing dependencies. Note using this
457 to materialize a large computation from scratch should be avoided due
458 to the recursion limit, use ``x.compute()`` instead.
459 """
460 if self._data is None:
461 # materialize any actual array args
462 args = (maybe_materialize(x) for x in self._args)
463 kwargs = {k: maybe_materialize(v) for k, v in self._kwargs.items()}
464
465 self._data = self._fn(*args, **kwargs)
466
467 # free any references to deps
468 self._fn = self._args = self._kwargs = None
469 self._deps = ()
470
471 return self._data
472
473 descend = descend
474 ascend = ascend
475
476 def compute(self):
477 """Compute the value of this lazy array, clearing any references to the
478 function, arguments and dependencies, and storing the result in the
479 ``_data`` attribute as well as returning it.
480
481 Unlike ``self._materialize()`` this avoids deep recursion.
482 """
483 for node in self.ascend():
484 node._materialize()
485 return self._data
486
487 compute_constants = compute_constants
488
489 def as_string(self, params):
490 """Create a string which evaluates to the lazy array creation."""
491 # name function and store in locals
492 fn_name = f"{getattr(self._fn, '__name__', 'fn')}{id(self._fn)}"
493 params.setdefault(fn_name, self._fn)
494
495 # string of args and kwargs
496 str_call = ", ".join(
497 itertools.chain(
498 (stringify(x, params) for x in self._args),
499 (
500 f"{k}={stringify(v, params)}"
501 for k, v in self._kwargs.items()
502 ),
503 )
504 )
505
506 # assign function call to new variable
507 return f"x{id(self)} = {fn_name}({str_call})"
508
509 get_source = get_source
510
511 def get_function(self, variables, fold_constants=True):
512 """Get a compiled function that computes ``fn(arrays)``, with ``fn``
513 describing the computational graph of this ``LazyArray`` and ``arrays``
514 corresponding to the downstream ``LazyArray`` nodes ``variables``.
515
516 Parameters
517 ----------
518 variables : sequence of LazyArray
519 Input nodes whose data can change between calls.
520 fold_constants : bool, optional
521 Compute all intermediates which do not depend on ``variables``
522 prior to compilation.
523
524 Returns
525 -------
526 fn : callable
527 Function with signature ``fn(arrays)``.
528 """
529 return Function(
530 inputs=variables, outputs=self, fold_constants=fold_constants
531 )
532
533 def show(self, filler=" ", max_lines=None, max_depth=None):
534 """Show the computational graph as a nested directory structure."""
535 if max_lines is None:
536 max_lines = float("inf")
537 if max_depth is None:
538 max_depth = float("inf")
539
540 # ┃ ━ ┗ ┣ │ ─ └ ╰ ├ ← ⬤
541 bar = f"│{filler}"
542 space = f"{filler}{filler}"
543 junction = "├─"
544 bend = "╰─"
545
546 line = 0
547 seen = {}
548 queue = [(self, ())]
549 while queue and (line < max_lines):
550 t, columns = queue.pop()
551
552 prefix = ""
553 if columns:
554 # work out various lines we need to draw based on whether the
555 # sequence of parents are themselves the last child of their
556 # parent
557 prefix += "".join(
558 bar if not p else space for p in columns[:-1]
559 )
560 prefix += bend if columns[-1] else junction
561
562 if t.fn_name not in (None, "None"):
563 item = f"{t.fn_name}{list(t.shape)}"
564 else:
565 # input node
566 item = f"←{list(t.shape)}"
567
568 if t in seen:
569 # ignore loops, but point to when it was computed
570 print(f"{line:>4} {prefix} ... ({item} from line {seen[t]})")
571 line += 1
572 continue
573
574 print(f"{line:>4} {prefix}{item}")
575 seen[t] = line
576 line += 1
577
578 if len(columns) < max_depth:
579 deps = sorted(t.deps, key=get_depth, reverse=True)
580 islasts = [True] + [False] * (len(deps) - 1)
581 for islast, d in zip(islasts, deps):
582 queue.append((d, columns + (islast,)))
583
584 def history_num_nodes(self):
585 """Return the number of unique computational nodes in the history of
586 this ``LazyArray``.
587 """
588 num_nodes = 0
589 for _ in self.descend():
590 num_nodes += 1
591 return num_nodes
592
593 def history_max_size(self):
594 """Get the largest single tensor size appearing in this computation."""
595 return max(node.size for node in self.descend())
596
597 def history_size_footprint(self, include_inputs=True):
598 """Get the combined size of intermediates at each step of the
599 computation. Note this assumes that intermediates are immediately
600 garbage collected when they are no longer required.
601
602 Parameters
603 ----------
604 include_inputs : bool, optional
605 Whether to include the size of the inputs in the computation. If
606 ``True`` It is assumed they can be garbage collected once used but
607 are all present at the beginning of the computation.
608 """
609 delete_checked = set()
610 sizes = []
611 input_size = 0
612 for node in reversed(tuple(self.ascend())):
613 for c in node._deps:
614 if c not in delete_checked:
615 # last time a dependency is seen, subtract the size
616 if include_inputs or c._deps:
617 sizes.append(-c.size)
618 delete_checked.add(c)
619
620 if node._data is None:
621 # this is a new intermediate, add the size
622 sizes.append(+node.size)
623 elif include_inputs:
624 # this is an input, size is added at beginning
625 input_size += node.size
626
627 sizes.append(input_size)
628 sizes.reverse()
629 return list(itertools.accumulate(sizes))
630
631 def history_peak_size(self, include_inputs=True):
632 """Get the peak combined intermediate size of this computation.
633
634 Parameters
635 ----------
636 include_inputs : bool, optional
637 Whether to include the size of the inputs in the computation. If
638 ``True`` It is assumed they can be garbage collected once used but
639 are all present at the beginning of the computation.
640 """
641 return max(self.history_size_footprint(include_inputs=include_inputs))
642
643 def history_total_size(self):
644 """The the total size of all unique arrays in the computational graph,
645 possibly relevant e.g. for back-propagation algorithms.
646 """
647 return sum(node.size for node in self.descend())
648
649 def history_stats(self, fn):
650 """Compute aggregate statistics about the computational graph.
651
652 Parameters
653 ----------
654 fn : callable or str
655 Function to apply to each node in the computational graph. If a
656 string, one of 'count', 'sizein', 'sizeout' can be used to count
657 the number of nodes, the total size of the inputs, or the total
658 size of each output respectively.
659
660 Returns
661 -------
662 stats : dict
663 Dictionary mapping function names to the aggregate statistics.
664 """
665 if not callable(fn):
666 if fn == "count":
667
668 def fn(node):
669 return 1
670
671 elif fn == "sizein":
672
673 def fn(node):
674 return sum(child.size for child in node.deps)
675
676 elif fn == "sizeout":
677
678 def fn(node):
679 return node.size
680
681 stats = collections.defaultdict(int)
682 for node in self.descend():
683 node_cost = fn(node)
684 if node_cost is not None:
685 stats[node.fn_name] += fn(node)
686
687 return dict(stats)
688
689 def history_fn_frequencies(self):
690 """Get a dictionary mapping function names to the number of times they
691 are used in the computational graph.
692 """
693 return self.history_stats("count")
694
695 def to_nx_digraph(self, variables=None):
696 """Convert this ``LazyArray`` into a ``networkx.DiGraph``."""
697 import networkx as nx
698
699 if variables is None:
700 variables = set()
701 elif isinstance(variables, LazyArray):
702 variables = {variables}
703 else:
704 variables = set(variables)
705
706 G = nx.DiGraph()
707
708 nodemap = {}
709
710 for i, node in enumerate(self.ascend()):
711 nodemap[node] = i
712 variable = (node in variables) or any(
713 child in variables for child in node.deps
714 )
715 if variable:
716 variables.add(node)
717 G.add_node(i, array=node, variable=variable)
718 for x in node.deps:
719 G.add_edge(nodemap[x], nodemap[node])
720
721 return G
722
723 plot = plot_circuit
724 plot_graph = plot_graph
725 plot_circuit = plot_circuit
726 plot_history_size_footprint = plot_history_size_footprint
727 plot_history_functions = plot_history_functions
728 plot_history_functions_scatter = functools.partialmethod(
729 plot_history_functions, kind="scatter"
730 )
731 plot_history_functions_lines = functools.partialmethod(
732 plot_history_functions, kind="lines"
733 )
734 plot_history_functions_image = functools.partialmethod(
735 plot_history_functions, kind="image"
736 )
737 plot_history_stats = plot_history_stats
738 plot_history_stats_counts = functools.partialmethod(
739 plot_history_stats, fn="count"
740 )
741 plot_history_stats_sizein = functools.partialmethod(
742 plot_history_stats, fn="sizein"
743 )
744
745 @property
746 def fn(self):
747 """The function to use to compute this array."""
748 return self._fn
749
750 @property
751 def fn_name(self):
752 """The name of the function to use to compute this array."""
753 return getattr(self._fn, "__name__", "None")
754
755 @property
756 def args(self):
757 """The positional arguments to the function to use to compute this
758 array.
759 """
760 return self._args
761
762 @property
763 def kwargs(self):
764 """The keyword arguments to the function to use to compute this
765 array.
766 """
767 return self._kwargs
768
769 @property
770 def shape(self):
771 return self._shape
772
773 def __len__(self):
774 return self.shape[0]
775
776 def __iter__(self):
777 for ax in range(self.shape[0]):
778 yield self[ax]
779
780 @property
781 def ndim(self):
782 return len(self._shape)
783
784 @property
785 def size(self):
786 return functools.reduce(operator.mul, self.shape, 1)
787
788 @property
789 def backend(self):
790 return self._backend
791
792 @property
793 def deps(self):
794 """A tuple of the dependencies, other LazyArray instances, of this
795 array.
796 """
797 return self._deps
798
799 @property
800 def depth(self):
801 """The maximum distance to any input array in the computational graph."""
802 return self._depth
803
804 def __hash__(self):
805 return id(self)
806
807 def __getitem__(self, key):
808 return getitem(self, key)
809
810 # this makes numpy operations delegate to __rmatmul__ etc.
811 __array_ufunc__ = None
812
813 def __mul__(self, other):
814 return multiply(self, other)
815
816 def __rmul__(self, other):
817 return multiply(self, other)
818
819 def __add__(self, other):
820 return add(self, other)
821
822 def __radd__(self, other):
823 return add(self, other)
824
825 def __sub__(self, other):
826 return sub(self, other)
827
828 def __rsub__(self, other):
829 return sub(other, self)
830
831 def __floordiv__(self, other):
832 return floordivide(self, other)
833
834 def __rfloordiv__(self, other):
835 return floordivide(other, self)
836
837 def __truediv__(self, other):
838 return truedivide(self, other)
839
840 def __rtruediv__(self, other):
841 return truedivide(other, self)
842
843 def __mod__(self, other):
844 return mod(self, other)
845
846 def __pow__(self, other):
847 return pow_(self, other)
848
849 def __rpow__(self, other):
850 return pow_(other, self)
851
852 def __matmul__(self, other):
853 return matmul(self, other)
854
855 def __rmatmul__(self, other):
856 return matmul(other, self)
857
858 def __abs__(self):
859 return abs_(self)
860
861 def __neg__(self):
862 return self.to(operator.neg)
863
864 def __eq__(self, other):
865 return eq(self, other)
866
867 def __ne__(self, other):
868 return ne(self, other)
869
870 def __gt__(self, other):
871 return gt(self, other)
872
873 def __lt__(self, other):
874 return lt(self, other)
875
876 def __ge__(self, other):
877 return ge(self, other)
878
879 def __le__(self, other):
880 return le(self, other)
881
882 @property
883 def T(self):
884 return transpose(self)
885
886 @property
887 def H(self):
888 return conj(transpose(self))
889
890 def reshape(self, shape, **kwargs):
891 return reshape(self, shape, **kwargs)
892
893 def astype(self, dtype_name):
894 return lazy_astype(self, dtype_name)
895
896 @property
897 def dtype(self):
898 return self.to(get_dtype, shape=())
899
900 @property
901 def real(self):
902 return real(self)
903
904 @property
905 def imag(self):
906 return imag(self)
907
908 def __array_namespace__(self, api_version=None):
909 """Support array api namespace - https://data-apis.org/array-api/."""
910 from autoray import lazy as lazy_api
911
912 return lazy_api
913
914 def __repr__(self):
915 return (
916 f"<{self.__class__.__name__}("
917 f"fn={self.fn_name}, "
918 f"shape={self.shape}, "
919 f"backend='{self.backend}')>"
920 )
921
922
923 register_backend(LazyArray, "autoray.lazy")
924
925
926 def ensure_lazy(array):
927 if not isinstance(array, LazyArray):
928 return LazyArray.from_data(array)
929 return array
930
931
932 def find_lazy(x):
933 """Recursively search for ``LazyArray`` instances in pytrees."""
934 if isinstance(x, LazyArray):
935 yield x
936 return
937
938 if isinstance(x, (tuple, list)):
939 for subx in x:
940 yield from find_lazy(subx)
941 return
942
943 if isinstance(x, dict):
944 for subx in x.values():
945 yield from find_lazy(subx)
946 return
947
948
949 # --------------------- recusively evaluating 'pytrees' --------------------- #
950
951
952 def materialize_larray(x):
953 return x._materialize()
954
955
956 def materialize_tuple(x):
957 return tuple(map(maybe_materialize, x))
958
959
960 def materialize_list(x):
961 return list(map(maybe_materialize, x))
962
963
964 def materialize_dict(x):
965 return {k: maybe_materialize(v) for k, v in x.items()}
966
967
968 def materialize_identity(x):
969 return x
970
971
972 _materialize_dispatch = {
973 LazyArray: materialize_larray,
974 tuple: materialize_tuple,
975 list: materialize_list,
976 dict: materialize_dict,
977 }
978
979
980 def maybe_materialize(x):
981 """Recursively evaluate LazyArray instances in tuples, lists and dicts."""
982 try:
983 return _materialize_dispatch[x.__class__](x)
984 except KeyError:
985 _materialize_dispatch[x.__class__] = materialize_identity
986 return x
987
988
989 # -------------------- recusively stringifying 'pytrees' -------------------- #
990
991
992 def stringify_larray(x, params):
993 name = f"x{id(x)}"
994 if x._data is not None:
995 params.setdefault(name, x._data)
996 return name
997
998
999 def stringify_tuple(x, params):
1000 if not x:
1001 return "()"
1002 return f"({', '.join(stringify(xi, params) for xi in x)},)"
1003
1004
1005 def stringify_list(x, params):
1006 return f"[{', '.join(stringify(xi, params) for xi in x)}]"
1007
1008
1009 def stringify_dict(x, params):
1010 entries = (f"{k}: {stringify(v, params)}" for k, v in x.items())
1011 return f"{{{', '.join(entries)}}}"
1012
1013
1014 def stringify_identity(x, params):
1015 if isinstance(x, (int, float, complex, bool, slice, range)):
1016 return f"{x}"
1017 if isinstance(x, str):
1018 return f"'{x}'"
1019 name = f"c{id(x)}"
1020 params.setdefault(name, x)
1021 return name
1022
1023
1024 _stringify_dispatch = collections.defaultdict(
1025 lambda: stringify_identity,
1026 {
1027 LazyArray: stringify_larray,
1028 tuple: stringify_tuple,
1029 list: stringify_list,
1030 dict: stringify_dict,
1031 },
1032 )
1033
1034
1035 def stringify(x, params):
1036 """Recursively stringify LazyArray instances in tuples, lists and dicts."""
1037 return _stringify_dispatch[x.__class__](x, params)
1038
1039
1040 # --------------------------------- caching --------------------------------- #
1041
1042
1043 _SHARING_STACK = collections.defaultdict(list)
1044
1045
1046 def currently_sharing():
1047 """Check if we are currently sharing a cache -- thread specific."""
1048 return threading.get_ident() in _SHARING_STACK
1049
1050
1051 def get_sharing_cache():
1052 """Return the most recent sharing cache -- thread specific."""
1053 return _SHARING_STACK[threading.get_ident()][-1]
1054
1055
1056 def _add_sharing_cache(cache):
1057 _SHARING_STACK[threading.get_ident()].append(cache)
1058
1059
1060 def _remove_sharing_cache():
1061 tid = threading.get_ident()
1062 _SHARING_STACK[tid].pop()
1063 if not _SHARING_STACK[tid]:
1064 del _SHARING_STACK[tid]
1065
1066
1067 @contextlib.contextmanager
1068 def shared_intermediates(cache=None):
1069 """Context in which intermediate results are shared.
1070
1071 Note that intermediate LazyArray instances (which can reference actual
1072 data) will not be garbage collected until
1073 1. this context exits, and
1074 2. the yielded cache is garbage collected (if it was captured).
1075
1076 Parameters
1077 ----------
1078 cache : dict
1079 If specified, a user-stored dict in which intermediate lazy arrays will
1080 be stored. This can be used to interleave sharing contexts.
1081
1082 Returns
1083 -------
1084 cache : dict
1085 A dictionary in which sharing results are stored. If ignored,
1086 sharing results will be garbage collected when this context is
1087 exited. This dict can be passed to another context to resume
1088 sharing.
1089 """
1090 if cache is None:
1091 cache = {}
1092 _add_sharing_cache(cache)
1093 try:
1094 yield cache
1095 finally:
1096 _remove_sharing_cache()
1097
1098
1099 def maybe_id(x):
1100 if hasattr(x, "shape"):
1101 return id(x)
1102 if isinstance(x, list):
1103 return tuple(x)
1104 return x
1105
1106
1107 def hash_args_kwargs(fn_name, *args, **kwargs):
1108 hargs = tuple(map(maybe_id, args))
1109 if kwargs:
1110 hkwargs = tuple(sorted((k, maybe_id(v)) for k, v in kwargs.items()))
1111 else:
1112 hkwargs = None
1113 return f"{fn_name}-{hash((hargs, hkwargs))}"
1114
1115
1116 def lazy_cache(fn_name, hasher=None):
1117 """Decorator to mark a function as being lazy cacheable.
1118
1119 Parameters
1120 ----------
1121 fn_name : str
1122 The name to use for the function in the cache.
1123 hasher : callable
1124 A function with signature ``hasher(fn_name, *args, **kwargs)`` that
1125 returns a hashable key for the cache. If not specified, the default
1126 is to use ``hash_args_kwargs``.
1127 """
1128
1129 if hasher is None:
1130 hasher = hash_args_kwargs
1131
1132 def wrapper(fn):
1133 @functools.wraps(fn)
1134 def wrapped(*args, **kwargs):
1135 if not currently_sharing():
1136 return fn(*args, **kwargs)
1137
1138 cache = get_sharing_cache()
1139
1140 key = hasher(fn_name, *args, **kwargs)
1141 if key not in cache:
1142 cache[key] = fn(*args, **kwargs)
1143
1144 return cache[key]
1145
1146 return wrapped
1147
1148 return wrapper
1149
1150
1151 _DTYPES_REAL_EQUIV = {"complex128": "float64", "complex64": "float32"}
1152 _DTYPES_COMPLEX_EQUIV = {"float64": "complex128", "float32": "complex64"}
1153
1154
1155 @functools.lru_cache(None)
1156 def dtype_real_equiv(dtype_name):
1157 return _DTYPES_REAL_EQUIV.get(dtype_name, dtype_name)
1158
1159
1160 @functools.lru_cache(None)
1161 def dtype_complex_equiv(dtype_name):
1162 return _DTYPES_COMPLEX_EQUIV.get(dtype_name, dtype_name)
1163
1164
1165 @functools.lru_cache(None)
1166 def _find_common_dtype(array_types, scalar_types):
1167 import numpy as np
1168
1169 return np.find_common_type(array_types, scalar_types).name
1170
1171
1172 def find_common_dtype(*xs):
1173 return _find_common_dtype(tuple(map(get_dtype_name, xs)), ())
1174
1175
1176 @functools.lru_cache(None)
1177 def _find_common_backend_cached(names):
1178 return max(
1179 names,
1180 key=lambda n: multi_class_priorities.get(n, 0),
1181 )
1182
1183
1184 def find_common_backend(*xs):
1185 names = tuple(
1186 x.backend if isinstance(x, LazyArray) else infer_backend(x) for x in xs
1187 )
1188 return _find_common_backend_cached(names)
1189
1190
1191 @functools.lru_cache(1024)
1192 def find_broadcast_shape(xshape, yshape):
1193 xndim = len(xshape)
1194 yndim = len(yshape)
1195 if xndim < yndim:
1196 xshape = (1,) * (yndim - xndim) + xshape
1197 elif yndim < xndim:
1198 yshape = (1,) * (xndim - yndim) + yshape
1199 return tuple(max(d1, d2) for d1, d2 in zip(xshape, yshape))
1200
1201
1202 # -------------------------------- interface -------------------------------- #
1203
1204
1205 def Variable(shape, backend=None):
1206 """Create a ``LazyArray`` from a shape only, representing a leaf node
1207 in the computational graph. It can only act as a placeholder for data.
1208 """
1209 return LazyArray.from_shape(shape, backend=backend)
1210
1211
1212 @lazy_cache("array")
1213 def array(x):
1214 """Create a ``LazyArray`` from an input array, representing a leaf node
1215 in the computational graph.
1216 """
1217 return LazyArray.from_data(x)
1218
1219
1220 @lazy_cache("transpose")
1221 def transpose(a, axes=None):
1222 a = ensure_lazy(a)
1223
1224 if axes is None:
1225 axes = range(a.ndim)[::-1]
1226
1227 if all(i == ax for i, ax in enumerate(axes)):
1228 # no transposition required
1229 return a
1230
1231 fn_transpose = get_lib_fn(a.backend, "transpose")
1232 oldshape = shape(a)
1233 newshape = tuple(oldshape[i] for i in axes)
1234
1235 # check for chaining transpositions
1236 if a._fn is fn_transpose:
1237 b = a._args[0]
1238 if isinstance(b, LazyArray):
1239 axes_prev = a._args[1]
1240 axes_chained = tuple(axes_prev[k] for k in axes)
1241 return b.to(fn_transpose, (b, axes_chained), shape=newshape)
1242
1243 return a.to(fn_transpose, (a, axes), shape=newshape)
1244
1245
1246 permute_dims = transpose
1247
1248
1249 @lazy_cache("reshape")
1250 def _reshape_tuple(a, newshape, **kwargs):
1251 a = ensure_lazy(a)
1252 fn_reshape = get_lib_fn(a.backend, "reshape")
1253
1254 # check for redundant reshapes
1255 if a._fn is fn_reshape:
1256 b = a._args[0]
1257 if isinstance(b, LazyArray):
1258 a = b
1259
1260 return a.to(fn_reshape, (a, newshape), shape=newshape, kwargs=kwargs)
1261
1262
1263 @functools.lru_cache(2**14)
1264 def find_full_reshape(newshape, size):
1265 try:
1266 expand = newshape.index(-1)
1267 before = newshape[:expand]
1268 after = newshape[expand + 1 :]
1269 d = size // functools.reduce(
1270 operator.mul, itertools.chain(before, after), 1
1271 )
1272 return (*before, d, *after)
1273 except ValueError:
1274 return newshape
1275
1276
1277 def reshape(a, newshape, **kwargs):
1278 newshape = (newshape,) if isinstance(newshape, int) else tuple(newshape)
1279 newshape = find_full_reshape(newshape, a.size)
1280
1281 if shape(a) == tuple(newshape):
1282 # no reshape required
1283 return a
1284
1285 return _reshape_tuple(a, newshape, **kwargs)
1286
1287
1288 @lazy_cache("expand_dims")
1289 def expand_dims(a, axis):
1290 a = ensure_lazy(a)
1291 fn_expand_dims = get_lib_fn(a.backend, "expand_dims")
1292
1293 if axis < 0:
1294 axis += a.ndim + 1
1295
1296 new_shape = (
1297 *a.shape[:axis],
1298 1,
1299 *a.shape[axis:],
1300 )
1301 return a.to(fn_expand_dims, (a, axis), shape=new_shape)
1302
1303
1304 @lazy_cache("broadcast_to")
1305 def broadcast_to(array, shape):
1306 array = ensure_lazy(array)
1307 shape = tuple(shape)
1308 fn_broadcast_to = get_lib_fn(array.backend, "broadcast_to")
1309
1310 if array.shape == shape:
1311 # no broadcasting required
1312 return array
1313
1314 return array.to(fn_broadcast_to, (array, shape), shape=shape)
1315
1316
1317 def getitem_hasher(_, a, key):
1318 if not isinstance(key, tuple):
1319 key = (key,)
1320 hkey = tuple(
1321 str(k)
1322 if isinstance(k, slice)
1323 else id(k)
1324 if hasattr(k, "shape")
1325 else tuple(k)
1326 if isinstance(k, list)
1327 else k
1328 for k in key
1329 )
1330 return f"getitem-{hash((id(a), hkey))}"
1331
1332
1333 @functools.lru_cache(2**12)
1334 def get_sliced_size(d, start, stop, step):
1335 return len(range(d)[slice(start, stop, step)])
1336
1337
1338 @lazy_cache("getitem", hasher=getitem_hasher)
1339 def getitem(a, key):
1340 a = ensure_lazy(a)
1341
1342 deps = (a,)
1343
1344 if not isinstance(key, tuple):
1345 key = (key,)
1346
1347 nexpand = a.ndim
1348 expand = None
1349 for i, k in enumerate(key):
1350 if k is not None:
1351 if k is Ellipsis:
1352 expand = i
1353 else:
1354 nexpand -= 1
1355
1356 if expand is not None:
1357 # ellipsis somewhere
1358 key = key[:expand] + (slice(None),) * nexpand + key[expand + 1 :]
1359 elif nexpand:
1360 # need to pad trailing dimensions
1361 key = key + (slice(None),) * nexpand
1362
1363 adv_idx_shape = adv_idx_loc = None
1364 adv_idx_locs = []
1365
1366 shape = iter(a.shape)
1367 newshape = []
1368 for i, k in enumerate(key):
1369 if k is None:
1370 # (newaxis) -> new dimension of size 1
1371 newshape.append(1)
1372 # don't want to iterate shape
1373 continue
1374
1375 d = next(shape)
1376
1377 if isinstance(k, slice):
1378 # range of values
1379 newshape.append(get_sliced_size(d, k.start, k.stop, k.step))
1380
1381 elif hasattr(k, "shape") or isinstance(k, (tuple, list)):
1382 if adv_idx_shape is None:
1383 # first advanced index
1384 adv_idx_shape = _get_py_shape(k)
1385 adv_idx_loc = len(newshape)
1386 adv_idx_locs.append(i)
1387 else:
1388 # check if broadcast shape matches
1389 adv_idx_shape = find_broadcast_shape(
1390 adv_idx_shape, _get_py_shape(k)
1391 )
1392 # advanced indexing location is only retained when
1393 # all advanced indices are adjacent -> need to track
1394 adv_idx_locs.append(i)
1395
1396 if isinstance(k, LazyArray):
1397 # add to dependencies
1398 deps += (k,)
1399
1400 else:
1401 # else assume integer -> doesn't contribute to new shape,
1402 # but does count as an advanced index when it comes to
1403 # determining the location of the advanced index shape
1404 adv_idx_locs.append(i)
1405
1406 if adv_idx_shape is not None:
1407 if not all(i + 1 == j for i, j in zip(adv_idx_locs, adv_idx_locs[1:])):
1408 # 'move to front' advanced indexing
1409 newshape = (*adv_idx_shape, *newshape)
1410 else:
1411 # 'keep in place' advanced indexing
1412 newshape = (
1413 *newshape[:adv_idx_loc],
1414 *adv_idx_shape,
1415 *newshape[adv_idx_loc:],
1416 )
1417 else:
1418 newshape = tuple(newshape)
1419
1420 return a.to(operator.getitem, (a, key), shape=newshape, deps=deps)
1421
1422
1423 @lazy_cache("tensordot")
1424 def tensordot(a, b, axes=2):
1425 if isinstance(axes, int):
1426 axes = (tuple(range(a.ndim - axes, a.ndim)), tuple(range(axes)))
1427
1428 newshape = tuple(
1429 d for i, d in enumerate(shape(a)) if i not in axes[0]
1430 ) + tuple(d for i, d in enumerate(shape(b)) if i not in axes[1])
1431
1432 backend = find_common_backend(a, b)
1433 fn_tensordot = get_lib_fn(backend, "tensordot")
1434
1435 return LazyArray(
1436 backend=backend,
1437 fn=fn_tensordot,
1438 args=(a, b, axes),
1439 kwargs=None,
1440 shape=newshape,
1441 deps=tuple(x for x in (a, b) if isinstance(x, LazyArray)),
1442 )
1443
1444
1445 def _basic_einsum_parse_input(operands):
1446 # handle the basic, fully specified equation format
1447 eq, *arrays = operands
1448 lhs, rhs = eq.split("->")
1449 return lhs, rhs, arrays
1450
1451
1452 @functools.lru_cache(None)
1453 def _get_parse_einsum_input():
1454 try:
1455 from cotengra.utils import parse_einsum_input
1456
1457 return parse_einsum_input
1458 except ImportError:
1459 pass
1460
1461 try:
1462 from opt_einsum.parser import parse_einsum_input
1463
1464 return parse_einsum_input
1465 except ImportError:
1466 pass
1467
1468 import warnings
1469
1470 warnings.warn(
1471 "Could not find a full input parser for einsum expressions. "
1472 "Please install either cotengra or opt_einsum for advanced "
1473 "input formats (interleaved, ellipses, no-output)."
1474 )
1475
1476 return _basic_einsum_parse_input
1477
1478
1479 @lazy_cache("einsum")
1480 def einsum(*operands):
1481 lhs, rhs, larrays = _get_parse_einsum_input()(operands)
1482
1483 size_dict = {}
1484 for term, op in zip(lhs.split(","), larrays):
1485 op_shape = shape(op)
1486 for i, char in enumerate(term):
1487 size_dict[char] = max(size_dict.get(char, 1), op_shape[i])
1488 eq = f"{lhs}->{rhs}"
1489 newshape = tuple(size_dict[char] for char in rhs)
1490
1491 backend = find_common_backend(*larrays)
1492 fn_einsum = get_lib_fn(backend, "einsum")
1493
1494 return LazyArray(
1495 backend=backend,
1496 fn=fn_einsum,
1497 args=(eq, *larrays),
1498 kwargs=None,
1499 shape=newshape,
1500 deps=tuple(x for x in larrays if isinstance(x, LazyArray)),
1501 )
1502
1503
1504 @lazy_cache("trace")
1505 def trace(a):
1506 a = ensure_lazy(a)
1507 return a.to(
1508 fn=get_lib_fn(a.backend, "trace"),
1509 args=(a,),
1510 shape=(),
1511 )
1512
1513
1514 @lazy_cache("diag")
1515 def diag(a, k=0):
1516 a = ensure_lazy(a)
1517
1518 if a.ndim == 1:
1519 new_d = shape(a)[0] + abs(k)
1520 new_shape = (new_d, new_d)
1521 elif a.ndim == 2:
1522 new_d = max(min(shape(a)) - abs(k), 0)
1523 new_shape = (new_d,)
1524 else:
1525 raise ValueError("Input must be 1- or 2-d.")
1526
1527 return a.to(
1528 fn=get_lib_fn(a.backend, "diag"),
1529 args=(a, k),
1530 shape=new_shape,
1531 )
1532
1533
1534 @lazy_cache("diagonal")
1535 def diagonal(a, offset=0, axis1=0, axis2=1):
1536 a = ensure_lazy(a)
1537 fn_diagonal = get_lib_fn(a.backend, "diagonal")
1538
1539 if axis1 < 0:
1540 axis1 += a.ndim
1541 if axis2 < 0:
1542 axis2 += a.ndim
1543
1544 newshape = [d for ax, d in enumerate(a.shape) if ax not in (axis1, axis2)]
1545 newshape.append(max(min(a.shape[axis1], a.shape[axis2]) - abs(offset), 0))
1546
1547 return a.to(
1548 fn=fn_diagonal,
1549 args=(a, offset, axis1, axis2),
1550 shape=tuple(newshape),
1551 )
1552
1553
1554 @lazy_cache("matmul")
1555 def matmul(x1, x2):
1556 backend = find_common_backend(x1, x2)
1557
1558 shape1 = shape(x1)
1559 shape2 = shape(x2)
1560 if len(shape2) == 1:
1561 if shape1[-1] != shape2[-1]:
1562 raise ValueError(
1563 "matmul: Input operand 1 has a mismatch in its core dimension "
1564 "0, with gufunc signature (n?,k),(k,m?)->(n?,m?)"
1565 )
1566 newshape = shape1[:-1]
1567 elif len(shape1) == 1:
1568 if len(shape2) > 2 or shape1[-1] != shape2[-2]:
1569 raise ValueError(
1570 "matmul: Input operand 1 has a mismatch in its core dimension "
1571 "0, with gufunc signature (n?,k),(k,m?)->(n?,m?)"
1572 )
1573 newshape = shape2[-1:]
1574 else:
1575 if shape2[:-2] != shape1[:-2]:
1576 raise ValueError(
1577 "operands could not be broadcast together with remapped "
1578 f"shapes [original->remapped]: {shape1}->({shape1[:-2]},"
1579 "newaxis,newaxis) "
1580 f"{shape2}->({shape2[:-2]},newaxis,newaxis) and requested "
1581 f"shape ({shape1[-2], shape2[-1]})"
1582 )
1583 if shape1[-1] != shape2[-2]:
1584 raise ValueError(
1585 "matmul: Input operand 1 has a mismatch in its core dimension "
1586 "0, with gufunc signature (n?,k),(k,m?)->(n?,m?)"
1587 )
1588 newshape = (*shape1[:-1], shape2[-1])
1589
1590 return LazyArray(
1591 backend=backend,
1592 fn=operator.matmul,
1593 args=(x1, x2),
1594 kwargs=None,
1595 shape=newshape,
1596 deps=tuple(x for x in (x1, x2) if isinstance(x, LazyArray)),
1597 )
1598
1599
1600 @lazy_cache("kron")
1601 def kron(x1, x2):
1602 backend = find_common_backend(x1, x2)
1603 shape1 = shape(x1)
1604 shape2 = shape(x2)
1605
1606 ndim1 = len(shape1)
1607 ndim2 = len(shape2)
1608
1609 diff = ndim1 - ndim2
1610 if diff > 0:
1611 shape2 = (1,) * diff + shape2
1612 elif diff < 0:
1613 shape1 = (1,) * -diff + shape1
1614
1615 newshape = tuple(d1 * d2 for d1, d2 in zip(shape1, shape2))
1616 fn_kron = get_lib_fn(backend, "kron")
1617 return LazyArray(
1618 backend=backend,
1619 fn=fn_kron,
1620 args=(x1, x2),
1621 kwargs=None,
1622 shape=newshape,
1623 deps=tuple(x for x in (x1, x2) if isinstance(x, LazyArray)),
1624 )
1625
1626
1627 @lazy_cache("clip")
1628 def clip(a, a_min, a_max):
1629 a = ensure_lazy(a)
1630 fn_clip = get_lib_fn(a.backend, "clip")
1631 return a.to(fn_clip, (a, a_min, a_max))
1632
1633
1634 @lazy_cache("flip")
1635 def flip(a, axis=None):
1636 a = ensure_lazy(a)
1637 fn_flip = get_lib_fn(a.backend, "flip")
1638 return a.to(fn_flip, (a, axis))
1639
1640
1641 @lazy_cache("sort")
1642 def sort(a, axis=-1):
1643 a = ensure_lazy(a)
1644 return a.to(get_lib_fn(a.backend, "sort"), (a, axis))
1645
1646
1647 @lazy_cache("argsort")
1648 def argsort(a, axis=-1, **kwargs):
1649 a = ensure_lazy(a)
1650 return a.to(
1651 fn=get_lib_fn(a.backend, "argsort"),
1652 args=(a, axis),
1653 kwargs=kwargs,
1654 )
1655
1656
1657 @lazy_cache("stack")
1658 def stack(arrays, axis=0):
1659 arrays = tuple(arrays)
1660 newshape = list(shape(arrays[0]))
1661 newshape.insert(axis if axis >= 0 else axis + 1, len(arrays))
1662
1663 backend = find_common_backend(*arrays)
1664 fn = get_lib_fn(backend, "stack")
1665 return LazyArray(
1666 backend=backend,
1667 fn=fn,
1668 args=(arrays, axis),
1669 kwargs=None,
1670 shape=tuple(newshape),
1671 deps=tuple(x for x in arrays if isinstance(x, LazyArray)),
1672 )
1673
1674
1675 @lazy_cache("concatenate")
1676 def concatenate(arrays, axis=0):
1677 arrays = tuple(arrays)
1678 newshape = list(arrays[0].shape)
1679 newshape[axis] = sum(shape(a)[axis] for a in arrays)
1680
1681 backend = find_common_backend(*arrays)
1682 fn = get_lib_fn(backend, "concatenate")
1683 return LazyArray(
1684 backend=backend,
1685 fn=fn,
1686 args=(arrays, axis),
1687 kwargs=None,
1688 shape=tuple(newshape),
1689 deps=tuple(x for x in arrays if isinstance(x, LazyArray)),
1690 )
1691
1692
1693 @lazy_cache("split")
1694 def split(ary, indices_or_sections, axis=0):
1695 ary = ensure_lazy(ary)
1696
1697 d = shape(ary)[axis]
1698 num_subarrays = len(indices_or_sections) + 1
1699 div_points = [0] + list(indices_or_sections) + [d]
1700
1701 sub_arys = []
1702 selector = [slice(None)] * ary.ndim
1703 for i in range(num_subarrays):
1704 st = div_points[i]
1705 end = div_points[i + 1]
1706 selector[axis] = slice(st, end)
1707 sub_arys.append(ary[tuple(selector)])
1708
1709 return tuple(sub_arys)
1710
1711
1712 def where(condition, x, y):
1713 x = ensure_lazy(x)
1714 condition = ensure_lazy(condition)
1715 return LazyArray(
1716 backend=find_common_backend(condition, x),
1717 fn=get_lib_fn(x.backend, "where"),
1718 args=(condition, x, y),
1719 kwargs=None,
1720 shape=find_broadcast_shape(condition.shape, x.shape),
1721 deps=tuple(a for a in (condition, x, y) if isinstance(a, LazyArray)),
1722 )
1723
1724
1725 def _get_py_shape(x):
1726 """Infer the shape of a possibly nested list/tuple object."""
1727 if hasattr(x, "shape"):
1728 return tuple(x.shape)
1729 if isinstance(x, (tuple, list)):
1730 return (len(x),) + _get_py_shape(x[0])
1731 return ()
1732
1733
1734 @lazy_cache("take")
1735 def take(x, indices):
1736 x = ensure_lazy(x)
1737 if isinstance(indices, (list, tuple)):
1738 new_shape = _get_py_shape(indices)
1739 else:
1740 indices = ensure_lazy(indices)
1741 new_shape = indices.shape
1742 return LazyArray(
1743 backend=x.backend,
1744 fn=get_lib_fn(x.backend, "take"),
1745 args=(x, indices),
1746 kwargs=None,
1747 shape=new_shape,
1748 deps=tuple(a for a in (x, indices) if isinstance(a, LazyArray)),
1749 )
1750
1751
1752 @lazy_cache("take_along_axis")
1753 def take_along_axis(arr, indices, axis=-1):
1754 arr = ensure_lazy(arr)
1755 indices = ensure_lazy(indices)
1756
1757 if axis < 0:
1758 axis += arr.ndim
1759
1760 fn = get_lib_fn(arr.backend, "take_along_axis")
1761 new_shape = tuple(
1762 # target axis gets length from indices
1763 db
1764 if ax == axis
1765 # other axes are broadcast
1766 else max(da, db)
1767 for ax, (da, db) in enumerate(zip(arr.shape, indices.shape))
1768 )
1769
1770 return LazyArray(
1771 backend=arr.backend,
1772 fn=fn,
1773 args=(arr, indices, axis),
1774 kwargs=None,
1775 shape=new_shape,
1776 deps=(arr, indices),
1777 )
1778
1779
1780 def make_binary_func(name, fn):
1781 @lazy_cache(name)
1782 def binary_func(x1, x2):
1783 x1shape = getattr(x1, "shape", ())
1784 x2shape = getattr(x2, "shape", ())
1785 newshape = find_broadcast_shape(x1shape, x2shape)
1786 return LazyArray(
1787 backend=find_common_backend(x1, x2),
1788 fn=fn,
1789 args=(x1, x2),
1790 kwargs=None,
1791 shape=newshape,
1792 deps=tuple(x for x in (x1, x2) if isinstance(x, LazyArray)),
1793 )
1794
1795 return binary_func
1796
1797
1798 add = make_binary_func("add", operator.add)
1799 eq = make_binary_func("eq", operator.eq)
1800 equal = make_binary_func("equal", operator.eq)
1801 floordivide = make_binary_func("floordivide", operator.floordiv)
1802 ge = make_binary_func("ge", operator.ge)
1803 gt = make_binary_func("gt", operator.gt)
1804 le = make_binary_func("le", operator.le)
1805 lt = make_binary_func("lt", operator.lt)
1806 mod = make_binary_func("mod", operator.mod)
1807 multiply = make_binary_func("multiply", operator.mul)
1808 ne = make_binary_func("ne", operator.ne)
1809 pow_ = make_binary_func("pow", operator.pow)
1810 sub = make_binary_func("sub", operator.sub)
1811 truedivide = make_binary_func("truedivide", operator.truediv)
1812
1813
1814 def complex_(re, im):
1815 newshape = find_broadcast_shape(shape(re), shape(im))
1816 backend = find_common_backend(re, im)
1817 fn_complex = get_lib_fn(backend, "complex")
1818 return LazyArray(
1819 backend=backend,
1820 fn=fn_complex,
1821 args=(re, im),
1822 kwargs=None,
1823 shape=newshape,
1824 deps=tuple(x for x in (re, im) if isinstance(x, LazyArray)),
1825 )
1826
1827
1828 def make_unary_func(name):
1829 @lazy_cache(name)
1830 def unary_func(x):
1831 x = ensure_lazy(x)
1832 return x.to(fn=get_lib_fn(x.backend, name))
1833
1834 unary_func.__name__ = name
1835
1836 return unary_func
1837
1838
1839 sin = make_unary_func("sin")
1840 cos = make_unary_func("cos")
1841 tan = make_unary_func("tan")
1842 arcsin = make_unary_func("arcsin")
1843 arccos = make_unary_func("arccos")
1844 arctan = make_unary_func("arctan")
1845 sinh = make_unary_func("sinh")
1846 cosh = make_unary_func("cosh")
1847 tanh = make_unary_func("tanh")
1848 arcsinh = make_unary_func("arcsinh")
1849 arccosh = make_unary_func("arccosh")
1850 arctanh = make_unary_func("arctanh")
1851 sqrt = make_unary_func("sqrt")
1852 exp = make_unary_func("exp")
1853 log = make_unary_func("log")
1854 log2 = make_unary_func("log2")
1855 log10 = make_unary_func("log10")
1856 conj = make_unary_func("conj")
1857 sign = make_unary_func("sign")
1858 abs_ = make_unary_func("abs")
1859 angle = make_unary_func("angle")
1860 real = make_unary_func("real")
1861 imag = make_unary_func("imag")
1862
1863
1864 def make_reduction_func(name):
1865 @lazy_cache(name)
1866 def reduction_func(a, axis=None):
1867 a = ensure_lazy(a)
1868 fn = get_lib_fn(a.backend, name)
1869
1870 nd = a.ndim
1871 if axis is None:
1872 return a.to(
1873 fn=fn,
1874 shape=(),
1875 )
1876 elif not hasattr(axis, "__len__"):
1877 axis = (axis,)
1878 axis = tuple(nd + i if i < 0 else i for i in axis)
1879
1880 newshape = tuple(d for i, d in enumerate(shape(a)) if i not in axis)
1881 return a.to(fn=fn, args=(a, axis), shape=newshape)
1882
1883 return reduction_func
1884
1885
1886 sum_ = make_reduction_func("sum")
1887 prod = make_reduction_func("prod")
1888 min_ = make_reduction_func("min")
1889 max_ = make_reduction_func("max")
1890
1891 # # XXX: still missing
1892 # allclose
1893 # dot, vdot, inner, outer
1894 # pad, eye
1895 # squeeze, expand_dims
1896 # to_numpy
1897
1898
1899 # ----------------------------- array creation ------------------------------ #
1900
1901
1902 def empty(shape, *, backend="numpy", **kwargs):
1903 """Lazy creation of an empty array with a given shape."""
1904 return LazyArray(
1905 backend=backend,
1906 fn=get_lib_fn(backend, "empty"),
1907 args=(shape,),
1908 kwargs=kwargs,
1909 shape=shape,
1910 deps=(),
1911 )
1912
1913
1914 def zeros(shape, *, backend="numpy", **kwargs):
1915 """Lazy creation of an array filled with zeros with a given shape."""
1916 return LazyArray(
1917 backend=backend,
1918 fn=get_lib_fn(backend, "zeros"),
1919 args=(shape,),
1920 kwargs=kwargs,
1921 shape=shape,
1922 deps=(),
1923 )
1924
1925
1926 def ones(shape, *, backend="numpy", **kwargs):
1927 """Lazy creation of an array filled with ones with a given shape."""
1928 return LazyArray(
1929 backend=backend,
1930 fn=get_lib_fn(backend, "ones"),
1931 args=(shape,),
1932 kwargs=kwargs,
1933 shape=shape,
1934 deps=(),
1935 )
1936
1937
1938 def eye(N, *, backend="numpy", **kwargs):
1939 """Lazy creation of the identity matrix of size N."""
1940 return LazyArray(
1941 backend=backend,
1942 fn=get_lib_fn(backend, "eye"),
1943 args=(N,),
1944 kwargs=kwargs,
1945 shape=(N, N),
1946 deps=(),
1947 )
1948
1949
1950 def identity(n, *, backend="numpy", **kwargs):
1951 """Lazy creation of the identity matrix of size n."""
1952 return LazyArray(
1953 backend=backend,
1954 fn=get_lib_fn(backend, "identity"),
1955 args=(n,),
1956 kwargs=kwargs,
1957 shape=(n, n),
1958 deps=(),
1959 )
1960
1961
1962 # ---------------------------- autoray specials ----------------------------- #
1963
1964
1965 def lazy_get_dtype_name(x):
1966 return x.dtype
1967
1968
1969 @lazy_cache("astype")
1970 def lazy_astype(x, dtype_name):
1971 x = ensure_lazy(x)
1972 return x.to(fn=astype, args=(x, dtype_name))
1973
1974
1975 register_function("autoray.lazy", "get_dtype_name", lazy_get_dtype_name)
1976 register_function("autoray.lazy", "astype", lazy_astype)