Python 3.5 to Ship with Matrix Multiplication Operator
legacy.python.org
legacy.python.org
And since formulas can get complicated quickly, having a closer 1-1 correspondence with the mathematics is critical for understanding the meaning of the code. The PEP contains a nice example from statistics. And trust me, when you are writing numerical code, being able to read the mathematical formula clearly is essential, especially when you have a lot of formulas and need to figure out why your code is giving you numerical non-sense.
It's not really necessary to argue. Cayley's theorem guarantees that every group is a subgroup of a symmetric group:
http://en.wikipedia.org/wiki/Cayley's_theorem
A symmetric group is then a subgroup of the general linear group in any field, where the general linear group GL(K, N) is the set of invertible NxN matrices with entries from a "field" (just think "numbers") and therefore any [finitely generated] group is isomorphic to a group of matrices under matrix multiplication; this is the underlying concept of representation theory.
If we back up a little, a group is a very general sort of algebraic structure; many important concepts have an underlying group structure, such as rotations, permutations, and any sort of reversible computation. This latter case implies that matrix multiplication is Turing complete; the simplest such set of matrices is generated by the Toffoli gate matrix. The relationship of groups to geometry is due to the underlying correspondence between the axioms of a group and those of geometrical transformations. A set of reversible geometric transformations includes an identity element -- do nothing -- and obeys associativity (sorta complicated, but it makes sense if you think about it) and inverse operations (by assumption): this makes it a group, and it can be represented by matrices. If we remove "reversible", we get exceptions -- like the cross product -- but these are usually related to groups (cross product -> quaternion algebra).
So matrix multiplication is actually really, really fundamental in a lot of mathematics. It's also a special case of tensor contraction, which could justify another tower post (but won't).
>And trust me, when you are writing numerical code, being able to read the mathematical formula clearly is essential, especially when you have a lot of formulas and need to figure out why your code is giving you numerical non-sense.
(spent three months chasing a bug where two commands were out of order)
As a representation theorist, I am very sympathetic to this point of view, but I'm not sure that it proves that "[almost] every single linear algebra routine can be interpreted as a matrix-matrix multiplication"—unless one first has some reduction from an arbitrary linear-algebra routine to a group action.
> A symmetric group is then a subgroup of the general linear group in any field, where the general linear group GL(K, N) is the set of invertible NxN matrices with entries from a "field" (just think "numbers") and therefore any [finitely generated] group is isomorphic to a group of matrices under matrix multiplication; this is the underlying concept of representation theory.
Also, as a very minor nitpick, I think that you want 'finite' instead of 'finitely generated'; even infinite groups embed in (infinite) symmetric groups, but it's not obvious to me that infinite symmetric groups embed in (finite-dimensional) matrix groups, and it's certainly not true (just by counting cardinality) that infinite but finitely generated groups embed in finite symmetric groups.
1. Transpose is a linear map on matrices (vectors in R^nm), so in a very concrete sense it is precisely a matrix multiplication. And it's not hard to figure out the matrix, because it's analogous to the matrix that swaps entries in vectors.
2. Finding the first eigenvalue can be approximated via matrix multiplication, and for sparse matrices with good spectral gap this extends to all of them.
3. Row reduction can be phrased as matrix multiplication, and hence finding the basis for the kernel of a matrix is a byproduct of it, as is computing eigenvectors when given eigenvalues.
4. Computing orthonormal basis is a sequence of projection operators (and all linear maps are matrix multiplications)
5. I'm pretty sure nobody computes the Jordan canonical form on computers.
The point is that the connection between matrices and linear maps is the spirit of linear algebra.
> not the most efficient way to go about it
understatement of the century.
No, we're talking about language-level syntactic standardization of the most fundamental computational concept in linear algebra (and I would argue all of mathematics). My list just gives evidence to how unifying the concept is.
If you want supercomputing-grade efficiency you won't stop using numpy/scipy just because of this update, or you've already rewritten your Python prototype in C/Fortran anyway.
Especially since the update is just creating a language feature for numpy and similar libraries to leverage -- there is still no matrix implementation (and thus no matrix multiplication) in the standard library, just an overloadable operator so that numerical libraries can consistently use it for matrix multiplication and use * for elementwise multiplication, providing a standard API for those libraries.
1. Numpy people overload * for element-wise mul and matmul inconsistently and confusing people 2. The prefix func calls convention for matmul makes the formulas difficult to read 3. Python's precedence for splitting / into / and // can't apply to matmul because * * is already taken. 4. ` is banned, ?! lend unrelated meanings to context, $ is Perl and PHP baggage, so @ is the only thing left?
I got lost on the choice for @. If ?! lends unrelated meaings, and $ is Perlism, why doesn't @ suggest some kind of concat ops or Bashish/Perlish array sigils?
I'd personally much prefer >< . It looks like x, so it's much clearer. I don't understand the PEP's reason for not using ><.
Let them fix their own problems
Since its a fairly dominant application area that is pretty key for Python (there's a reason there are so many bundled python distributions that include the common scientific/numeric libraries, and that those environments are often chosen as pedagogical tools even for general-purpose programming), making a fairly modest language-level change to enable a clean resolution to this fragmentation is a sensible thing to do.
If you add some whitespace and squint just right, it even kinda sorta looks like math. If you further wrap all matrices and vectors in parentheses, you can pretend it's a whole new operator that lets you do matrix multiplication by juxtaposition.
S = ((H) (beta) - r).T (inv((H) (V) (H.T))) ((H) (beta) - r)
S = (H @ beta - r).T @ inv(H @ V @ H.T) @ (H @ beta - r)The (ab)use seems endless :)
Dozens of operators in Python have been overloadable and open for abuse for decades now, and yet I don't see much abuse, unlike the C++ and Scala communities. This says a lot about the Python community's ability to avoid pitfalls over the years.
I think the only real (ab)use of @ is to echo its use in another language. For example, @ means something in XPath, so X@Y could be used as a short-hand for X.attrib[Y] in an ElementTree-like API:
tree = load_xml_tree(...)
for node in tree.select("//item[@price > 2*@discount]"):
print(node @ "price", node @ "discount")Maybe passing objects with 'argument @ resource' would be interesting...
I guess you could torture @ for similar purposes in an email library or something.
As I said, there is DSL potential. As it stands, it's just something that is not possible.
class object:
def __matmul__(self, dict):
return self in dict.values()
a = {'asdf': 1}
if 1 @ a: # Evaluates to True.
print('Lovely!')I've always thought that maps and a matching __maps__ would have been a nicer way of referring to the keys of a mapping with in/__in__ referring to the values. Although the semantics are a bit odd in that case. Technically the mapping maps a key, but the language semantic to to have it the other way around as in key is mapped by mapping.
foo = {'bar': 42}
assert 42 in foo
assert 42 maps foo
assert foo maps 42
assert 42 mapped by foo
if 42 in d.values(): passWhat bugs me is the implicitness of __in__ defaulting to keys for a mapping. We have .keys() and .values() which are nice and clear since they explicitly grab an object which has an unambiguous definition for __in__.
Double Edit: It's an implementation decision that had to be made and I'm not aware of the rationale or debate behind the original choice. It's directly attributable to the decision to make __iter__ return the keys for a mapping which is the root of my issue. It's presumably useful and convenient (from a language writer's perspective) for iteration of a mapping to be along the keys in whatever order they may be traversed but if that's all it comes down to, why should a mapping be iterable at all when there is obvious ambiguity in what may be iterated? Maybe there is some history I'm not aware of where the .keys(), .values() and .items() methods were introduced post-hoc and the previous behaviour was such due to their non-existence and the need to iterate and then index to get all values in the object.
If you want to efficiently look for values, use a set() or store a second dict that goes from values to keynames.
If you're not worried about the efficiency, do the "in d.values()" you've suggested.
Using "in d.keys()" takes a quick hash lookup and turns it into a slower iterative list lookup.
The more reasonable (I think) problem I have is one of language semantics which is introduced by in being applicable to a mapping in the first place - why should a mapping be iterable at all if it is ambiguous (as I believe) as to what it should return? Members should be key:val pairs but membership checks refer only to keys and it's probably not unreasonable for a user to want any of .keys(), .values() or .items() when iterating. That's obviously why they're made available so why should __iter__ special case one of them?
I assume this is to match semantics introduced by the membership check and probably historical because without a .values() method, key iteration and lookups would be the usual way to get all values out of a mapping. This just seems like the kind of thing that could have been changed in Python3 (although 2to3 would probably not have been able to handle the syntax changes automatically).
map[key]==value
Its iterable at all because early python didn't have generators, so iterating over dict.keys() would be inefficient for large dictionaries (since you would create an intermediate list just to iterate over.)
> Maybe there is some history I'm not aware of where the .keys(), .values() and .items() methods were introduced post-hoc and the previous behaviour was such due to their non-existence and the need to iterate and then index to get all values in the object.
Prior to Python 3.x, .keys(), .values(), and .items() returned lists (rather than generators providing a view on the underlying dict), which would generally be inefficient if the only purpose was to iterate over them once.
'a' in {'a':1}
Sure, but it doesn't work the other way; there's no nicer way to write 2.florble(3). So you have a few operator methods, and then other methods are second-class citizens. Which in turn encourages people to abuse the operators as shortcuts for commonly-used operations, á la C++'s <<
In practice, very few languages have suffered problems from operator overloading. I can't think of another language where this is a problem (other than C++), which makes me think it's a cultural/code style problem, rather than a problem with the language itself. C++ seems to encourage abuse because everyone learns its IO library, and its IO has an API design so horrible it should make you retch.
By comparison, I'm not sure that adding more operators makes the resulting code any more palatable. Look at Haskell: libraries define their own operators, and the operators in Haskell have a steep learning curve. Can you tell me, without looking at a chart, whether $ or >>= has higher precedence, and what kind of associativity they have?
No, which is why I don't think that should be allowed. Scala doesn't do that - all "custom operators" have the same precedence, and the global rule is that anything ending in : associates to the right (and is defined by the thing on its right), otherwise to the left. So I could answer those questions easily for a Scala library.
Or am I missing something?
You're right that scala does special-case the precedence of a small number of operators (the list is much shorter than the likes of C, but I still wish we could move away from it).
Io uses Operator Shuffling to move those operator method calls back into normal mathematical expectation (or to be exact... C precedence order) prior to building the AST. Ruby's parser must do (or does) something similar. From lmm answer it sounds like Scala does something similar to Ruby here.
Smalltalk, Self & Rebol have no operator precedence and simply interpret the operators from left to right (using parenthesis to enforce higher precedence).
Some refs:
- http://iolanguage.org/scm/io/docs/IoGuide.html#Syntax-Operat...
map (*2) [1,2,3,4,5]
For eg.
1 + 1
add 1 1> Matrix multiplication is more of a special case. It's only defined on 2d arrays (also known as "matrices")
but this is not true. Matrix multiplication is just a special case of contraction of indices in a tensor (https://en.wikipedia.org/wiki/Tensor_contraction)—probably the most frequently used case, but not the only one. I'm certainly not arguing for the inclusion of general tensor-manipulating operators in Python, but it does seem to suggest a sensible alternative to:
> For inputs with more than 2 dimensions, we treat the last two dimensions as being the dimensions of the matrices to multiply, and 'broadcast' across the other dimensions.
namely, just contract on the inner indices. That is, arr(n1, ..., nk, m) @ arr(m, p1, ... pl) = arr(n1, ..., nk, p1, ..., pl).
EDIT: scythe (https://news.ycombinator.com/item?id=7554013) already pointed this out in passing.
No. This is what a mathematician might assume the PEP proposes without actually reading it. It instead proposes an entirely non-obvious definition which not equivalent to what you wrote.
In particular consider this example from the PEP.
arr(10, 2, 3) @ arr(10, 3, 4) = arr(10, 2, 4)> … a sensible alternative to [PEP proposal]; namely, just contract on the inner indices.
and not
> … a sensible alternative to contracting on the inner indices.
My argument for why it's sensible is precisely what you mentioned, namely, that it is what a mathematician would expect.
This PEP seems to imply that the cost would be a profusion of superfluous `newaxis`s, but I can't see that: it seems to me that you would need only to remember which kind of promotion works by default, and sprinkle in a `.T` whenever you need the other kind. (Anyone who's uncomfortable with lots of `.T`s in matrix-crunching code is not, I submit, someone who writes or reads lots of matrix-crunching code.)
Microsoft is even reportedly considering it* for inclusion in C#, now. I think every object-oriented programming language should have it.
* http://blogs.msdn.com/b/jerrynixon/archive/2014/02/26/at-las...
def get(obj, k, default=None):
""" safe __getitem__ obj[k] with a default """
def assoc(obj, k, v):
""" obj[k] = v returning obj """
def dissoc(obj, k):
""" safe del obj[k] returning obj without k"""
def get_in(obj, keys, default=None):
""" __getitem__ obj[k0][k1][kn] with a default. """
def assoc_in(obj, keys, v, default=lambda n: dict()):
""" __setitem__ obj[k0][k1][kn] = v. __getitem__ failures handled with default """
def dissoc_in(obj, keys):
""" Return obj asserting that obj[k0][k1][kn] does not exist. """
def update_in(obj, keys, update_fn=None, default=lambda n:dict()):
""" Update the value at obj[k0][k1][kn] with update_fn returning obj. __getitem__ failures handled by default. """
def merge_with(fn, **dictionaries):
""" Merge resolving node conflicts with fn """
def deep_merge_with(fn, **dictionaries):
""" Recursively merge resolving node conflicts with fn"""
Producing NULL (or whatever the languages equivalent is) isn't an error -- if there was an error, it would be throwing an exception, not returning NULL. The idea of "do this chain of operations propagating nulls encountered at any point" is reasonably useful.
> But the complexity of any proposed solution for this puzzle is immense, to me: it requires the parser (or more precisely, the lexer) to be able to switch back and forth between indent-sensitive and indent-insensitive modes, keeping a stack of previous modes and indentation level. Technically that can all be solved (there's already a stack of indentation levels that could be generalized). But none of that takes away my gut feeling that it is all an elaborate Rube Goldberg contraption.
One of the reasons I have been such a fan of Python for so long is the relatively no-nonsense approach to design decisions that many others would have rushed through.
I'd have personally preferred to see Python do type testing on the variables - it already does. For example:
'quick' + 'fox' = 'quickfox' 3 + 5 = 8 [3] + [5] = [3,5]
So why not make it a case where * on an int or float does the 'standard' multiplication that already exists whereas * on an array does matrix multiplication?
You arrive at the problem of then not having an element-wise version of the multiplication but it's not as if this solves that problem anyway.
What am I missing to make that a problem?
> You arrive at the problem of then not having an element-
> wise version of the multiplication but it's not as if this
> solves that problem anyway.
# Matrix multiplication:
a = b @ c
# Element-wise multiplication:
a = b * c[3] * [5] = [15]
? Because really it needs to reduce down to that if it's going to make sense from a continuity point of view.
edit: To clarify: Is that already part of 3.x, or shall it become part of 3.x once this is implemented?
"Numerical type" isn't quite the right description either, but the underlying point is that the design choices for lists don't necessarily favor mathematical convenience or consistency.
edit: Why not ×? It's unicode source afterall...
Symbols which are not present on US English keyboards start at a significant disadvantageAm I missing some useful applications of matrix multiplication on a general purpose language?
It seems that the most fundamental reason is that matrix and memberwise multiplication are two distinct operations which use the same datatypes as operands and both have a very good claim to use of the * operator.
Also, just because a language is general purpose does not mean that it cannot support features which might be restricted in their use.
Two of the python's most popular uses are in scientific and numeric fields (see SciPy, NumPy and ipython). This operator seems like it would be very useful for improving readability in those areas which is probably reason enough to use it.
However, please resist the urge to just overload this new operator for something unrelated that you want. The point of infix operators is to improve the readability of code and lessen the cognitive load on the reader. Overloading an operator for a purpose which is not conventional goes exactly against this for... what benefit exactly?
And the benefit of overloading is still readability, when carefully used and in a different domain. And sparingly. For the `@` operator I will be trying it as an "at" operator for accessing objects from a game map, or some sort of translation. If it performs well I may start using it in my pet projects. If it changes my life and enlightens everyone who gazes upon it, I may start using in production.
I do understand your worry and I promise to be extra careful.
I suppose you could use it for that that, but wouldn't that be a canonical case for indexing with []?
`[]` is for discrete elements. That's perfect for a tile game.
My idea with `@` is a sort of collision detection for continuous maps. `map @ (115.2, 23.5)` should return the object under that position.
This operation is useful on all sorts of interactions: "can I move there?", "what did the mouse click?", "do I have a line of sight?", etc.
I'm still thinking on how to chain those operations.
MATLAB went down the matrix rabbit hole so far, they made ordinary scalars second-class types. If you want to multiply scalars or otherwise do element-wise operations, you have to prefix the '*' operator with a '.'. If Python can make their language more linear-algebra friendly while avoiding that sort of silliness, I'm all for it.
what???
I'm still new to matlab, but the place where this has bitten me is if I'm trying to write code that works on either a scalar or vector of scAlars, if you aren't specific, the code my run fine against a single scalar, but blow up or do the wrong thing with a vector.
Just for the record, these are the characteristics of Python that made me call it "scripting":
- Interpreted
- Highly expressive
- No boilerplate
- Vast majority of programs are short
- Lots of libraries for gluing stuff together
- Used for turing-complete customization of software in other languages (e.g.: Sublime Text)
- Recommended as replacement for Bash in some cases
Anyway, I'm happy to see the language evolving to meet its users' needs.
> Indeed, and because it doesn't support closures, it's not a true functional programming language either. And because you have to import all sorts of modules to do the simplest things (e.g., regular expressions), neither is it a true scripting language. Indeed, because it doesn't support labeled break or continue statements, it's not even a true structured programming language.
I think the point is, trying to classify programming languages (except domain specific ones like SQL or maybe PHP) is kind of pointless.
But to answer your real question, Python is one of the top languages in number crunching. After web work, that's Python's second biggest niche.
It does now, and thank goodness, because even C++ has closures these days.
It can be used as a scripting language, but that doesn't seem to be the main use-case anymore.
"We all live in our own little sub-communities, so some Python users may be surprised to realize the sheer extent to which Python is used for number crunching -- especially since much of this particular sub-community's activity occurs outside of traditional Python/FOSS channels. So, to give some rough idea of just how many numerical Python programmers are actually out there, here are two numbers: In 2013, there were 7 international conferences organized specifically on numerical Python [3] [4]. At PyCon 2014, ~20% of the tutorials appear to involve the use of matrices [6]."
But they didn't consider a combination of multiple characters, like e.g. 3 * s?
(NOTE: Hacker news does not allow typing 3 * in a row)
I suspect this was to distance matrix mult
from traditional scalar mult operators.
Remember that ** is just shorthand for n *s.
whereas matrix mult is a different beast
entirely.
There is also added clutter with 3* where
typos may be non-obvious (already a potential
issue with ** I guess).
> Add lots of new operators, or add a new generic syntax for defining infix operators: In addition to being generally un-Pythonic and repeatedly rejected by BDFL fiat, this would be using a sledgehammer to smash a fly.
I think this is more clear than @ and is already familiar to programmers that deal with operator overloading methods. It would also enable the addition of arbitrary infix operators to python.
The @ decorator vs @ MMUL seems pretty syntactically clear though.
@decorator()
def function():
variable @ variable
trans_coef.T.dot(solve(H.dot(V).dot(H.T)), trans_coef)
trans_coef.T @ solve(H @ V @ H.T, trans_coef)
trans_coef' * ((H * V * H') \ trans_coef)
I'd go as far as saying that matrix computation plays an important role in more or less every kind of programming except for web/app development.
edit: As another comment points out, the PEP actually answers this question too and contains a slightly more comprehensive list of disciplines where matrices find frequent use: http://legacy.python.org/dev/peps/pep-0465/#but-isn-t-matrix...
It is empirically observed (and the identified rationale for this PEP) that matrix multiplication is done by overloading existing operators in popular Python libraries (going so far in Numpy as to have separate types differing primarily in whether the * operator does matrix or elementwise multiplication), and that this causes confusion, API fragmentation, and inefficiency, so, yes, it happens enough and is inconvenient enough that a general solution for doing it as an operator that doesn't interfere with existing operators is desirable.
Its not really "complicating the syntax", its just adding two new operators and corresponding magic methods, the structure of the syntax is unchanged, and these operators work just like other python operators, including their relationship to their corresponding magic methods.
Really, you should read the PEP (Python Enhancement Proposal) that is the linked article. It covers your question in great depth.
"In numerical code, there are two important operations which compete for use of Python's * operator: elementwise multiplication, and matrix multiplication"
The idea is to keep using * for elementwise multiplication, and use @ for matrix multiplication.
looks to me like an issue with python lack of static type checking. if you need to define an operator every time two types conflict, you're in for a long list...
Deleted comment
As in how ruby does it: http://www.ruby-doc.org/stdlib-2.0/libdoc/matrix/rdoc/Matrix...
You lost me at 3.