Einstein Notation applied in programming | Hacker News Reader

Einstein Notation applied in programming

hz2.org

72 pointsanacleto27 comments

Numpy has the einsum function, often very efficient as it avoids allocating memory for intermediate results.

http://docs.scipy.org/doc/numpy/reference/generated/numpy.ei...

I've never seen a cross product being defined in that way using Einstein notation.

You might want to express the cross product using the Levi-Civita symbol epsilon_{ijk} [1].

epsilon_{ijk} = 1 for i,j,k = 1,2,3 and all even permutations thereof. epsilon_{ijk} = -1 for all odd permutations of i,j,k = 1,2,3. Else it is 0.

Then, the cross product reduces to: C_i = epsilon_{ijk} A_j B_k

Using identities for epsilon_{ijk} you can – for example – easily calculate what A cross (B cross C) is.

[1]: https://en.wikipedia.org/wiki/Levi-Civita_symbol

> I've never seen a cross product being defined in that way using Einstein notation.

In fact, I can't understand this use of the notation—namely,

    C_i = A_{i + 1 `mod` 3}B_{i + 2 `mod` 3}

—and am not sure that it's correct. There is no free variable on the right-hand side, so I'm not sure over what to sum. Even if this were fixed, we'd need something like, as you say, the Levi–Civita symbol, since a given entry of the cross product is not a sum but a difference.

Oh, you're right. I just glanced over the equation and I thought I should recommend the standard notation.

But as you stated, the cross product is clearly wrong as given by the author. There's obviously no other way than defining it with a totally antisymmetric quantity like the Levi-Civita symbol.

When there is no free variable, there is no sum, just the loop.

But you are right the the notion does not work as is because complicated subscript support is not implemented yet. But the equation is listed before the programming part is mentioned and it is an illustration of idea, so I believe it is ok.

It is not difficult to add the implementation, although it will be tedious (but still behind the surface). It is matter of how useful it is. And you are probably right that implementing a Levi-Civita syntax might be more straight forward.

Oh I noticed my mistake, now corrected.

In Julia it is easy: https://github.com/Jutho/TensorOperations.jl

In some fields, e.g. condensed matter physics, you need you need to deal with contracting multidimensional tensors all the time, and with out Einstein notation it would be difficult.

The simples example is so-called matrix product state (http://en.wikipedia.org/wiki/Matrix_product_state), which is similar to Markov process. But for more interesting scenarios (e.g. 2d) one needs to use at least 4 dim tensors.

What the author call "black magic" I call abstraction. Why would you need to know at all times what summation and multiplications of what rows and columns are going on in your matrices? That's why use matrices, to not have to think about those all the time.

I think you missed the point.

You can write `a mmu b` in KDB, but what the author refers to as no clue on the surface to tell me what is A, B, or C is about the need for improved notation, not an extended maths library.

That said, I think the author's notation is terrible, so I'll use a different one. In K you can write

    +/+*\:

or explicitly

    {+/+x*\:y}

which is a function: sum flip x times eachleft y

This allows me to see that:

    (2 3f;4 0f)*\:(1 2f;5 -1f)

is:

    ((2 4f;15 -3f);(4 8f;0 -0f))

and because I want the sums to go "the other way" I just sum the flip:

    +/+((2 4f;15 -3f);(4 8f;0 -0f))

Now I must prefer reading it this way; my MBA has too small a screen to fit the C code the way the author wrote it, but in just a few characters it is completely obvious what is going on!

This extends to the second example as well: +/1+!x (sum one plus til x) is much more clear than:

    int sum=0,i,a[100];
    for(i=0;i<100;++i)a[i]=i+1;
    for(i=0;i<100;++i)sum=sum+a[i];

and while sumcode doesn't take up so much room that I can't fit it on my screen, the K example is much clearer and much more obvious to the point where I might notice that {+/1+!x} is the same as {a+x*a:x%2} -- something I might miss if the two for-loops are far enough away from each other.

Do you still think we need a sumcode abstraction now? Or do you understand the value of better list comprehension?

I am not sure I find your syntax intuitive, but I understand that takes individual experience.

The main point (I am the author btw) is to have a lexical layer above the programming language layer, and give the programer control on how to write code that is most fit his mind. For example, how about give you the ability of use your +/+*\: when you are programming in C?

You may not buy it, but the idea is to separate the syntax layer from language layer so programmer can have a sliding context just like the way our mind deals with daily life.

I enjoyed your article.

Chinese is purportedly intuitive.

For example, 人 means "person", and 山 means mountain.

I don't see it, personally. I'm given to understand 成龍 means Jackie Chan.

However good notation doesn't have to be intuitive; we're talking in English and English is definitely not intuitive. That is to say that "person" doesn't look anything like a person.

Just as we learn to fit the concept of addition into our mind with the unintuitive + symbol, I find it useful to fit the concepts of K into my mind.

It is worth learning.

On your second point, you may not realise this yet, but you've invented a new programming language. There's no "syntax layer" and "language layer", because language is just the tool our mind uses to express problems and I believe that the lexemes used to express that language become a part of our brains when we try to solve problems in it. With that in mind, you will understand what I mean when I say: You have a language for expressing solutions; a notation, and I'll explain what I meant when I said I thought the notation was terrible:

First: C is also useful. Arthur writes K in C, so he might have a function like this:

    K fun(K x,K y){K("+/+*\\:");return apply2(g,x,y);}

The K macro is basically:

    #define K(s) static K g;if(!g)g=parse(s);

He doesn't write it this way. It would probably be more like:

    K2(fun){K("+/+*\\:");R ap2(g,x,y);}

but that's because the compact notation is useful.

This isn't the only good example I've seen: Zeta-C was a C implementation in Common Lisp. You could "switch to lisp" in Zeta-C just by writing an @-sign before the lisp form, i.e.

    int fun(int x, int y) {
      return @(stuff:mmu |x| |y|);
    }

ECL uses a pre-processor that allows you to write C code in it similarly. This is what mixing two languages looks like when done well: It looks like it belongs there, and it's useful for more than just being able to call Lisp functions from C: Those things could be Lisp macros(!) and even be mixed in C macros giving the programmer an incredible flexibility in expressing themselves!

What you've got is a notation with an edge. I can see where the C/Perl is, and where your "other notation" is (i,j,etc), and I don't like it. I feel the code switch snap loudly in my mind the same way I feel when I see a <?php

You could have made it look like it belonged there, and people could dip into your language easily. It would certainly be more work, but the notation would be better. Perhaps when you flesh out all the things you want to do you will consider revisiting this.

Thanks for detailed reply. I appreciate it.

First let's get the emotion color out. Whether someone think "intuitive" or "like" is arbitrary -- depend on experience and will change. For example, I have been thinking problems in Einstein notations for decades, so the syntax just seems natural to me, but I know other people may not think so, (I know this from my colleagues who have the same work context and known to be smart). So absolute verdict of "like" or not is of no value. It is more meaningful when we compare the alternatives -- rather than just saying you don't like it, it would be more interesting to hear what alternative you like. For me, it is comparison of Einstein notation and the full-blown nested loops.

Now what I really want to clarify is what I mean the language layer and syntax layer. (Often existing vocabulary fall short when describing ideas you are not used to so bear with me if you find term "language layer" inappropriate.) Think about programming a factorial function in C and in a functional language such as Haskell. In C, you probably will write a straight loop; in Haskell, it will be a recursion. The languages have its mandates and force us to write code accordingly. That is what I mean the language layer. Now think about the loops, we can say

    for(i=0;i<n;i++)

    for(i=0:n)

    loop(n)

Some of them may be unfamiliar, but they all mean the exact same thing -- resulting exact the same machine code. Syntax layer does not alter your code. We can use Chinese keywords instead of "if", "while", "for", and we will write the exact same C.

Now look at the current situation: except pure macros like m4, every so called programming language force to program differently at fundamental level: with different data types, static become dynamic, swapping out libraries which changes fundamental algorithm, etc. Then, all these new language sugar coat their syntax to make you think you are just changing into a better syntax to lure you in. Once you are in, you suddenly realize every thing has changed and it become obvious that you can't program in your old language with the same kind of experience anymore, and worse yet, you find yourself eager to defend your position and zealously fights the language war, at the syntax front.

PS: If expression fits your mind, then it is intuitive because you don't have to think extra. If expression does not fit your mind, and you have to think extra to understand then it is not intuitive. So English is intuitive as long as you think in English. I do.

PS2: There is an interesting study with people in Hong Kong who speaks both Chinese and English. The research found questionnaires in Chinese or English results in different statistics. So apparently, there is more than syntax layer difference between English and Chinese. On the other hand, dialects such as Cantonese and Mandarin are probably just syntax layer difference -- maybe this can even be applied to Latin and French.

When I was doing lots of tensor computations during my PhD, I found Cadabra (http://cadabra.phi-sci.com/) which has great support for Einstein notation.

Been a while since GR, but I'm pretty sure some of those indices are supposed to be on top. A_{ij} = B_i^k * C_{jk} possibly, but don't quote me on that.

Since these are Euclidean spaces, the difference between contravariant and covariant indices is non-existent. So it doesn't matter whether the indices are upstairs or downstairs.

I would say not 'nonexistent', but rather 'avoidable'; or, even better, that there is an isomorphism in an appropriate sense. (Compare the situation for strings and lists of characters; the types are isomorphic, but I wouldn't say that the difference between them is non-existent!)

True. I'm just a lazy relativist though ;)

Yeah, but I find that -- like dimensional analysis -- keeping careful track of what's upstairs and downstairs can help me keep a computation from going off the rails.

As cabinpark (https://news.ycombinator.com/item?id=9165144) points out, it is not necessary to make this distinction; but, if you want to do so, canonically a matrix has one covariant and one contravariant index, so you would want something like

    A_i^j = B_i^k*C_k^j .

Subscripts are how it's used in the more down to earth engineering applications like anisotropic thermal conductivity and elasticity. I can see why some authors might want to put the right-hand-side-only variables somewhere else for clarity though.

Nice post. I studied with this notation too but I was not clever enough to connect it to my programming.

This is a good example of a situation where something like lisp's macro system would be very useful. But I don't understand what the author means by

On the other end of the spectrum, lisp is designed for its upper layer elegance. Its macros are structured all the way to the top. However, to achieve that, it limits its lower level representations. In fact, it takes work-around for simple switches and loops.

What's the work-around? Common Lisp and Clojure have built in conditionals and loops.

Obviously it is my ignorance. I'll revise it back. But I still think MyDef is more than lisp. I need find a lisp expert friend (that is willing to understand MyDef) to make better narration. :)

So you've discovered what macros are for. M4 can do this and a lot more: http://en.wikipedia.org/wiki/M4_%28computer_language%29

I know. But I find it too difficult to use. Maybe it is just me. The big idea behind MyDef is if the programmer find something is more natural, he should at least try it.

I (the author) do not really care if anyone use MyDef per my implementation. One could implement MyDef in Lisp, Haskell, or any language, and I would be happy. A meta layer that individual programmer can control, rather than being sold in wholesale every single time.

This is totally missing the point. Nonsingular matrices form a group; use the multiplication operator to convey a wealth of operations that you can do with it.

There are C++ libraries which have claimed to do this.

I use this regularly in Matlisp: https://github.com/matlisp/matlisp/wiki

It is not a library. It is a syntax. An important idea of MyDef is the implementation behind the syntax is accessible to the programmer so the programmer can read, check, verify, modify and create. So when the programmer later decide to optimize the code into inline assembly (just e.g.), he can, without changing any of his def code.

Reply on news.ycombinator.com