Concise algorithms written in Julia
github.com
github.com
For instance, for some of the regression algorithms the pseudo-inverse of the matrix is used to solve the normal equations. Again, for small, well-behaved problems it is OK, but for larger scale, less well-behaved problems, it is actually dangerous (numerical instabilities and other issues). There are better, faster, more stable approaches. (PhD in Applied Math here)
BTW, I have been using Julia for work for several years now and I think it is a fantastic language for scientific computing. For those who use Matlab/Numpy regularly, you should definitely check it out.
𝛉 = pinv(𝐗)*y
𝛉 = y\𝐗
There's a whole branch in applied math that's called numerical linear algebra and deals with all these kinds of situations. One of the most important results is that you should almost never do an explicit computation of the inverse of a matrix. It is expensive and can be highly unstable. If you ever see a A\b or pinv(A)*b in somebody's code, it should raise a big red flag.
If the matrix is not full rank the psuedoinverse provides the least squares solution.
It can also be done efficiently and may well already be implemented using whatever numerical method one prefers (SVD, QR).
And the implementation probably allows for regularization via a singular value cutoff.
I'm not sure what matlab's backslash operator does these days, but it looks like a more efficient way to get a least-squares solution (compared to the pseudoinverse), possibly with sparsity imposed slightly.
May I ask how was transition like from Matlab/Numpy to Julia like did you migrate your work or start from the scratch using Julia?
Computer scientists (I've been one for roughly 50 years) introduce their own academic notations. Is circled plus, ⊕, a boolean exclusive-or or is it bitwise exclusive-or. Take a look at Knuth Vol 4A, it's chock full of mathematical notations embedded in algorithms. He uses superscripts that are themselves superscripts, how are those supposed to be entered with our text editors?. What about sequence notations like 1, 4, 9, 16, ... we might suppose that it is just the integer squares, but the On-line Encyclopedia of Integer Sequences lists 187 other possibilities. Is the compiler supposed to guess what this is?
Well, if mathematicians use these concise notations, why shouldn't programmers? I believe it is because mathematicians don't want or need to take the time and space needed to spell out these operators, variables, and functions in their papers. It's not necessary for mathematicians. Other specialists in their field can figure out what the symbols mean while reading their papers. Their students can understand what a blackboard capital F (𝔽), likely a field in a class on abstract algebra.
Programmers are doing something different. Their programs are going to be a lot longer than most math papers or lecture expositions. The programs have to deal with data, networks, business rules, hardware limits, etc. And everything in a program must be unambiguous and precise. Programs are large and can be edited many times by many people. For these reasons, I'm inclined to favor programing in plain language with plain ascii.
See:
Knuth, The Art of Computer Programming Vol 4A, Combinatorial Algorithms
The on-line encyclopedia of integer sequences, https://oeis.org
Mathematicians don't need to fight compilers, only other mathematicians. If Mathematicians needed to convince a compiler their equations, I'm sure they'd be forced to be fully explanatory and less handwavey at the margins.
What they seem to do, instead, is to demonstrate that you can write code in Julia that is quite close to the mathematical notation. (Whether you should do so is another question).
[1] for example, adding a row of ones to a matrix by using array comprehension:
𝐗 = [j==0 ? 1.0 : X[i][j] for i in 1:m, j in 0:n]
𝛉 = pinv(𝐗)\*ySometimes a practical algorithm does not look like a textbook algorithm, because they're different algorithms, but I think the main reason that there is such a discrepancy is:
1. math notation is many times quite ambiguous
2. there are a bunch of performance optimizations that end up being unsightly
I am not claiming it's easy work, but I think it's nice to try to find abstractions so that at least somewhere, the algorithm looks simple.
I don't, however, think that these code examples really make that shine at all. There are also choices I disagree with. For example, there is (paraphrasing) `map(vⱼ -> g(x, vⱼ), V)`. the `j` subscript is meaningless to me, and is an awkward combination of "point free" / "index free" notation with a higher-order function, and a more traditional spelling. Math texts love to do things like V = [v_1, ... , v_n]. That doesn't make sense to do in a programming language. instead of writing v_j, you just do V[j].
The other big thing missing in Julia that is IMO important here is more control over evaluation, like allowing lazy evaluation. You can build some of these features on top of Julia (e.g. https://github.com/RelationalAI-oss/Salsa.jl).
Math is usually not written with computation in mind, so some algorithm might e.g. re-evaluate f(x) multiple times. Compiler optimizations can help in some cases, as can a "dynamic" solution like memoization/caching. But again, I don't think Julia is "there" yet.
The vast majority of the code I write is not mathy. But I do write a fair bit of mathy code because of the field I operate in. Because of this, I'd side with the ones that hate it for some of these algos: the various sorts, for example. But for others, the use of mathematical symbols brings clarity, IMO. Assuming you already know the algo.
I've had to translate mathematical notation from a set of papers into code before. When I first picked up Julia, I re-did something I had previously done in Python/pandas/numpy. I used mathy notation... and julia code, ended up both MUCH clearer and quite a bit faster. I call that a win in my book.
It's uncanny valley but for code.
you have described perfectly the problem that I have when reading n0code written by programmers who are not mathematicians... my mind wants to read variables with multiple letters as products of each letter.
I find multi-letter variable names extremely old fasioned, as when math was written explicitly in latin before the advent of algeraic notation.
EDIT: an illustrative tweet of my concern: https://mobile.twitter.com/fermatslibrary/status/14109451739...
Sometimes I read things here on Hacker News that throw me so hard I leave the site for a month or two. Congratulations, this time it's your fault. Goodbye.
They are also less descriptive, and this makes the semantic interpretation more difficult.
Usually mathematicians read entire papers, or large excerpts, at a time. In this situation the semantic association symbols<->concepts is often made at the beginning of each section and reused for several formulas, making mathematical notation more effective.
Programmers instead often look at code in smaller fragments. They don’t have thesame level of contextual information readily available and so they often prefer to embed this information in variable names.
Add that programs are written mostly in ASCII, on a keyboard, with autocomplete, in a single typeface, and math by hand, on paper or blackboard, with much more graphic possibilities.
Quite the opposite. Verbose, "readable" code destroys pattern recognition.
People might deny having the same problem, but I've seen it hundreds of times where a mistake is made because two symbols were conflated or a subscript was overlooked, or a symbol with multiple uses in different contexts was assumed to be one thing when really it was another. That said it's still neat to see code using common symbols with what you'd find in textbooks.
tl;dr: COBOL won.
Julia's target audience isn't "business" or "business people", although there's no reason you couldn't use it for that purpose.
In this case, if the developers involved are assumed to know the math already, concise is probably for the good. If you are trying to teach the algorithms to a mathematically unsophisticated audience, it's a different story.
If I'm describing the same concept to a) a group of undergrad students, b) a group of mathematicians and grad students c) a group of software developers or d) a room full of execs - I'm going to do it differently in each case, including notation and emphasis.
The other part is that it was never intended for programmers at all; it was for the ‘vice-president or a colonel or admiral’ who wanted the illusion of being able to understand their underlings' work. I think it's unfortunate that it took over general-purpose computing during the dot-com boom; prolixity engenders clarity about as much in code as in human language.
I guess this site is trying to sell Julia a bit, by showing how close it looks to mathematical pseudo-code.
It's the famous "write-only" problem of the Perl language, which uses symbols heavily too.
Did author of this repo checked even once rendered images?
This looks fine in a tab by itself. https://raw.githubusercontent.com/mossr/BeautifulAlgorithms....
- Greek letters
- glyphs with obscure latex codes
The last one in particular - how do you read this in your mind if you don't already know the name of the character? - "Hmm, that's a curly handwritten A". It's so disruptive to the thought process of the reader of your code if they don't already know the notation.
I really think that this is the opposite of beautiful. Code is about communicating with other people too. I also think that mixing code and math notation is liked by a vocal minority of Julia users but in the long term is harming the adoption of the language by beginners.
Math requires excellent fonts if you don't want your reader to want to murder you by attempting to decipher the difference between L, calligraphic L, script L, italic L...
The way you put it, it almost sounds as if that wouldn'be great!
If you're a practitioner and not much of a programmer, it might be faster and easier to read the "math notation" version, which will be familiar to you, than the version a programmer might write, which might be unfamiliar and might require your brain to scan everything "from scratch".
If you're branching out into other code, you can always ask Julia itself what a particular character is — just paste it into a help prompt at the REPL:
help?> 𝒜
"𝒜" can be typed by \scrA<tab>
julia> '𝒜'
'𝒜': Unicode U+1D49C (category Lu: Letter, uppercase)There's a reason we use 'y = mx + b' instead of 'range = slope * domain + intercept' when we're doing math calculations. It's nice to use the long form when we're learning what the symbols are, but the symbols enhance readability when you're doing math, once you've become familiar with the meaning of the terms.
There is a reason why one letter/number variables are basically verboten in best practice.
Maybe the title should have been 'Algorithms that look concise and beautiful to people who already know them'.
I've seen plenty of function use, say, `theta` but I have never worked with θ.
I don't think an expert in some field who just happens not to be an expert in some other field's jargon and pictographs should be branded "a lowest common denominator of people", this terminology is both judgmental and elitist in all the bad ways.
Personally, those 'strange letters' make it more readable, because that's how the mathematics are written.
People like to pretend that mathematical notations are standardized and obvious to practitioners, but they're just not. In my physics undergrad days we made a joke shirt with all the usages of the symbol "k" as it appeared in our physics texts. Is it the constant in Coulomb’s law? Is it a spring constant? The Boltzman proportionality factor? Is it kinetic energy? Is it a kilo? A kelvin? I think we were able to cover the front and back of the shirt with the overloaded usages.
I've noticed physicists can be a bit fast and loose with their definitions, somehow you're assumed to be up to do date on what concept is given the symbol "R" in that particular context. Though they do tend to agree with each other which concept should have which symbol.
During my dissertation I had to collect implementations of about a dozen parameterizations of a process I was studying, with the intent of coupling them/incorporating them into a set of climate modeling experiments. All of the implementations were in Fortran (which in and of itself wasn't a problem, albeit it was annoying re-writing or re-factoring some F77 code to play more nicely with the more modern Fortran codebase in which our climate model was written). Of these codes I collected, the majority of them had bugs which restricted my ability to reproduce the reported results from the original work they accompanied. One or two of them had significant flaws in them - answer-changing bugs which, when corrected, potentially would yield different results from those reported in their original papers, and might actually lead to different conclusions.
One of the nice things about the Jupyter ecosystem of tools and Julia is the ability to more closely replicate equations from the original paper. It seems dumb, but in my anecdotal experience I've noticed fewer significant bugs when colleagues have used these features. I've also noticed a propensity for scientists and researchers to write clearer, better-documented code - if your next line of code is going to directly mimic Equation 13 in your paper, why wouldn't you go ahead and write a comment saying so?
What is easier: matching (𝛍, 𝚺) to (𝛍, 𝚺), or to (mu, Sigma)?
Let me say there is a third alternative: (mean, cov) (except you'll shadow some functions...).
It's becoming a pet peeve of mine how HN conflates a solid, classical mathematical education with some kind of gatekeeping club. Anyone is welcome to join. Anyone is welcome not to use this language if they wish. But please don't dictate how us mathematicians are supposed to communicate.
Calling this mathematical education makes me doubt your implicit claim of pedagogical ability.
I think a lot of math could be taught with a lot less overhead and in more understandable fashion. It's just that the natural incentives seem to drive people to unnecessary overhead and barriers for those who actually want to learn.
Lot of the language and symbols involved could be streamlined. But like QWERTY keyboard and C++, you would first have to turn this huge hulking ship of legacy cruft into that direction.
Ok. Have at it, I guess.
> Lot of the language and symbols involved could be streamlined. But like QWERTY keyboard and C++, you would first have to turn this huge hulking ship of legacy cruft into that direction.
This screams a fundamental misunderstanding of mathematics. The symbols need context to make any sense whatsoever. To a reader with intimate knowledge of the context, the symbols convey lots of information very efficiently. That doesn't mean that the symbols are understandable without context, or even that they could be made understandable without context.
Using in-group context-sensitive symbols is by definition exclusive. Using descriptive well thought out names is inclusive.
Math as a language seems very needlessly compressed. Imagine a world where programmers invented a new symbol for every function and you would have to look up what they mean, but when you look up what they mean, you would have to look up 10 other symbols. Most of those symbols refer back to symbols where you came from in the first place. It's a detriment for learning. Simple as that.
Not everybody wants to be a mathematician. Some people just want to get work done and read through a bunch of research papers.
Are you saying the whole field of mathematics (and physics) is wrong, and we're doing something "meaningless"?
> Using in-group context-sensitive symbols is by definition exclusive. Using descriptive well thought out names is inclusive.
Not when the group is open to anyone who wants to join. Math is probably the most "open source" field out there. Barring the very cutting edge front of research, everything can be learned from free sources or ones that can be borrowed for free from libraries, or had through very very cheap second hand material.
That there is a high barrier to entry when it comes to effort isn't some malicious gatekeeping design. It's just because some things are hard.
> Math as a language seems very needlessly compressed. Imagine a world where programmers invented a new symbol for every function and you would have to look up what they mean, but when you look up what they mean, you would have to look up 10 other symbols.
You clearly have never done math! The way it works requires intimate familiarity with the definitions of the symbols. Once you actually manage to internalize that (it can be a lot of work), remembering what the symbols stand for comes for free.
> Not everybody wants to be a mathematician. Some people just want to get work done and read through a bunch of research papers.
"Not everyone wants to be a surgeon, some people just wanna read medical research papers."
"Not everyone wants to be an astrophysicist, some people just wanna read astrophysics papers."
Do you not see how ridiculous this is? Nobody is gatekeeping for the sake of gatekeeping. You're conflating gatekeeping with something just being hard, and the practitioners of the hard thing not wanting to change the way we work to accommodate non-practitioners (to our own detriment!)
All I'm seeking here is how to improve communicating math without having to go through the credentialism of higher education.
edit: Why you didn't understand my comment on reading papers: some computer science papers require heavy math background. A lot of math is actually applied math.
Lastly:
> All I'm seeking here is how to improve communicating math without having to go through the credentialism of higher education.
Like I've already pointed out: mathematics is perhaps the most "open source" field there is. There's no need to go through the "credentialism" if you don't want to. Again you're just conflating math being hard with it being protected by some imagined wall of credentialism guarded by gatekeepers.
I think it's just the opposite. People familiar with the relevant math have, most likely, worked with this stuff in other programming languages and never used math symbols in their code.
I'm used to seeing θ or α in text and theta or alpha in code. The combination of Greek letters and for loops looks very weird.
(Seriously talking: From an educational point of view, lowest common deminator is exactly what you want, as long as you can communicate the entire concept effectively)
The options aren't just complete beginner vs math PhD though. Imagine an experienced software developer who has written these kinds of algorithms in other languages and has never used latex. That's the kind of person you're also keeping out. Are they "the lowest common denominator"?
I also don't know why you assumed that the people who are most likely to use this code like this are automatically people who already know the glyphs.
It's gatekeeping not just because there is barrier to entry. It's because that barrier is artificial, unnecessary and comes with a smug feeling of superiority (you aren't the first person to use "lowest common denominator" in this thread).
I don’t think that Julia having the capacity to use this style is bad, but I don’t think these examples are “beautiful and concise”, more “baroque and tasteless”.
Its not like anyone could draw them properly by hand either
I don't need to only if I already know what they mean. How does your brain process a character that you can't pronounce and whose meaning you're trying to understand from the code you're currently reading? Because my brain will need to assign something to it in order to use it.