Translating math into code with examples in Java, Racket, Haskell, Python (2011)
matt.might.net
matt.might.net
Math is so easy! and its a joy to work with when programming, but the way its written, the notation, is often baffling to me.
Another consideration: A formal rule based math syntax could be checked by a computer (theorem prover).
Keep in mind we use special single letter variables all the time, sometimes multiple for the same concept. Multiply, divide, add, subtract. You learned them all in early education along with everyone else, and now you have a universal set of symbols to express arithmetic concepts.
Would we be better off if every occurrence of '+' was replaced with 'sum'? I don't think so, but that doesn't necessarily mean that loading up with single letter variables that people aren't familiar with is better. It's entirely to do with how familiar the target audience is with them. A library targeted for use by scientists might see benefit to more of them, while one targeted towards being accissible to many people might not.
If you stick to convention and use stuff like A for array, i for index, r for root, δ for small change (a delta), ε for error, Σ (Greek S) for sum, Π (Greek P) for product, etc.
It's only when you start using variable names as if they were free variables when they really aren't that you get into trouble with comprehension, especially from people not in your field.
I'm more used to math than to code, and I find multiple-letter variables ridiculous when not unreadable.
In the ancient times, mathematicians used to write formulas using latin sentences. Even the simplest arithmetic result occupied a few lines of text. Are you proposing that we go back to that age?
What if students learned "Force = mass * acceleration", and only later moved to "F = ma" once they'd gotten tired of writing it, instead of smacking students in the face with "F = ma" right out of the gate, to say nothing of all the other stuff we smack them with right away?
Sets? Define a set semantically, then replace "set" with S. Vector spaces? Define a vector space semantically, then replace "vector space" with V. Limits? Define a limit semantically, then replace the word with "lim".
Moreover mathematicians typically use jargon in a more reader-friendly way than simply throwing obtuse equations at them. Expressions, equations, inequalities and identities are complements to the proof, not the proofs themselves. Best practice holds that you present a theorem in plain language alongside the necessary notation, then break its proof down into as many atomic units (lemmas, propositions, corollaries, etc) as possible. Here is a blog post[1] from Terence Tao giving general advice for why that's useful. Tao has written a bunch[2] of these on the theme of emphasizing exposition and clarity.
Also contrary to popular belief, well-written mathematics papers actually have quite a lot of exposition in them. For a famous example, look at Yitang Zhang's proof[3] that there are infinitely many primes with 70 million numbers (or fewer) in between them. He spends a full five pages on introduction, background results used to develop the proof, and (most importantly) notation. He also includes a "sketch" of the proof in broad strokes so that a reader can follow his arguments at both a high level and in gritty detail.
That doesn't mean papers like Zhang's are accessible to most people. The jargon is still there and you can't really change that unless you want papers to become self-contained monographs. But the point is that what you're proposing - concepts defined in a straightforward way before moving on to dense notation - is already the general practice.
__________________________________
1. https://terrytao.wordpress.com/advice-on-writing-papers/crea...
But this is not clear enough. What force? What acceleration? More precisely, what is the direction of the acceleration? The original statement of this law is less ambiguous: "Mutationem motus proportionalem esse vi motrici impressae, et fieri secundum lineam rectam qua vis illa imprimitur. "
Or, in plain english: "The alteration of motion is ever proportional to the motive force impress'd; and is made in the direction of the right line in which that force is impress'd"
There! we are good to go. Now write the fundamental theorem of calculus in english, readable by everybody, without those ugly, unreadable variables and fancy symbols...
[1]: AIUI, the actual problem the original "New Math" had. The original "New Math" tried to start students with set theory, because that was the foundations of mathematics, so obviously, the best place to start an education, right? (Hint: No.) This is why parents said they didn't understand "New Math". By comparison "Common Core" math is all-but-identical to what I learned in school 30 years ago.
(and I may add that all programming should do the same).
I also agree with you that starting math with set theory is utterly ridiculous and even harmful. You should start with arithmetic and with geometry (obviously, using single-letter variables when needed).
Anyway, in sometimes it is useful to write more. For example teaching https://en.wikipedia.org/wiki/Consistent_and_inconsistent_eq... I try to write the full name of the classification at least for two clases. It is painful, but it is worth. I teach in Spanish, so we have also the problem that underdetermined is "indeterminado", so a capital "I" can mean "Inconsistent" or "[I]underdetermined" or in one of the following clases "Independent" (like in a linear independent set of vectors, yes they mix this too). So it is important to use the full name (or a long enough abbreviation) until you are sure that everyone can understand which "I" you are writing.
For example, factoring a polynomial can be done by calling the `factor` function:
>>> factor(x**2 - 5*x + 6, x)
(x-3)*(x-2)
Suddenly all the boring and fear-inducing math operations are available to you after a few simple calculations in a REPL! That's a huge win if you ask me ;)
______
[1] Printable math+SymPy tutorial https://minireference.com/static/tutorials/sympy_tutorial.pd... [2] Notebook version of [1] https://nbviewer.jupyter.org/github/minireference/SymPyTut/b...
In mathematics, the driver for notation is: how succinctly can I express, what I want to express in this particular effort, yet allowing others to verify my work without mis-interpretation.
I am not sure if those two worlds are reconcilable, and mergeable, with worlds of structured and 'just-in-time' teaching.
I am going to also, claim, that style of presentation of mathematics is more appropriate for formulating vision, structure, strategy, architecture in formal technical/financial 'contracts'.
As I progress (perhaps, already at a sunset) of my career, I can see that lack of fluency in mathematics (both algebra and analysis) is a major impediment for transition into more highly compensated (and impactful) , yet, still technical roles for many of us, out there.
Do you have an example off the top of your head? I'm assuming that by, "fluency in mathematics (both algebra and analysis)", you mean something beyond basic calculus and linear algebra.
My experience has been that software engineers at the staff, principal and architect levels don't really need to know advanced mathematics at all. From what I've seen they usually have a breadth of experience as generalists and a depth of experience in one or two particular specializations, which may or may not involve any advanced mathematics at all.
"Fluency" in mathematics, in my experience, isn't about being able to perform more complex computation, that's what computers are for. The key to fluency in mathematics is increased efficiency at equational reasoning.
Granted, I work in data science, but I've personally seen that more and more problems I have are solved writing out a few equations and reasoning about the problem than writing code. It's not about knowing, for example, what SVD is, but seeing how a variety of common problems trivially map to it. Or figuring out how to transform a business problem into a probability problem so you can quickly estimate your success. Many times now I have spent a few afternoons writing equations that simplified what would have been very large and unnecessarily complex programs.
The mistake programmers make is thinking that math is just fancy computation, but mathematical reasoning is an entirely distinct way of reasoning about problems and computation is usually the least important part.
I used to also think that there was no reason for programmers to learn any math outside of enough calculus and linear algebra to compute basic things. But really understanding these areas and reasoning about them fluently (as well as other areas of mathematics) opens up many possibilities of problem solving that code it self does not.
1) Modeling capacity/latency of complex system with queuing theory (basically creating spreadsheets that can 'calculate' how much servers you need with what I/O throughput/etc for our software)
2) When looking at tables in data-warehouse, as 'types' -- I felt I could benefit from leveraging modern type theory, where I could at least categorize schemas (filds/relations) into 'Automatically-transformable into target warehouse schema' vs 'human intervention is needed'.
Besides natural complexity, the papers in type theory use that fraction notation :-). For some reason difficult for me.
3) Various data de-anonymization proofing techniques, differential crypto, and tamper-proof logging.
Ability to read financial mathematics and NLP technique is something I do not need now, but I would have benefitted significantly in my past.
Don't be afraid to dive into maths if you feel like it.
Anecdotally people >25 do better than younger people. Maturity appears to be an asset sometimes.
Yes, young people might think and learn slightly quicker, but older people tend to be less easily distracted and more focused on the task at hand.
Maths is not a race though, so I believe age is an advantage at the end of day.
If you mean advanced proofs, again the article may be the right place to start.
https://www.researchgate.net/publication/37597511_The_Role_o...
What they did was make all the math explicit, mostly by inserting all the necessary pieces of differential geometry that were glossed over in all other treatments.
Algorithms, though? No problem. Programming in typical Algol-family languages & similar came easily to me. The "tough" early topics? Pointers, recursion? Not even a bump in the road, totally natural. To this day, though, the ones that look more like mathematical writing (Haskell) are really hard to read, let alone write. I can get all the concepts at play in a piece of Haskell and still not be able to keep the syntax or meaning of the code itself straight. When I do want or have to read mathematics of any complexity whatsoever, I only make headway by converting it to something more algorithmic as I go ("OK, so what does this term or whatever do to any other values passing through, here?")
My field has a lot of dense math that makes the pyramids look simple (ok I exaggerate, but there is a lot going on). The only way I've been able to really grok it is by writing software to do it. Now that I know what's going on, the math notation is useful in that it explains the problem in a succint way. I think Calculus via Python with nothing but the stdlib and Matplotlib would be a better way for me to learn to be honest.
Of course the best way to do this would be to try and model the notation yourself (if possible) into function specs or algorithms, as you go through various math books. Then you'd really understand the notation even if you failed to implement it. You could try Pyret to do this https://papl.cs.brown.edu/2018/func-as-data.html#%28part._.A...
Some problems with solutions in different languages. Each problem leads to the next one.
https://www.amazon.com/Coding-Matrix-Algebra-Applications-Co...
https://www.youtube.com/channel/UCGVa4wp8SWGFtMe6hcdpHlg/pla...
I would also be interested in a "math for programmers" approach to deciphering formalism. I've studied a fair amount of linear algebra / differential geometry and could see how Python-definitions might help. I'm less familiar with other areas of mathematics
I think one argument against this is that in math you often want to reach down a few abstraction levels and reorder terms, factor out things etc. which requires peeking into the "internals of boxes". You can't abstract to the point where you only have two or three variables in one equation because to show the next step, you would need to make the expanded formulas of those variables interact (cancellations etc.).
Another is that math is quite a different way of thinking. Most professions don't do as much of this input/output-based, requirements-based thinking with lots of ad-hoc on-the-fly introduced abstractions that is usual in programming. For example engineers, doctors etc. just work very differently and consider many different levels of abstraction at the same time. They consider it normal to sprinkle in temperatures, voltage values etc. in supposedly high-level discussions. Programming is a product of the mind so we have an easier time with it for sure, as our abstractions are more reliable (even if they leak to some degree, they leak much much more in other disciplines).
Now, math is also a product of the mind, but tradition is quite different. Of course math is very abstraction-heavy but the abstractions are usually not generated by the practitioner on-the-fly, on-demand, the way you just write a function or introduce a class in programming. Rather they are widely-known definitions and conventions, which are mostly only created by the people developing new theory. Of course you do define some notations and variables in math, but I find it not as pervasive as in programming.
The closest you can get to programming-like variables in math writing that still somewhat adheres to math tradition is to place full words into subscript positions (index). For example, you can write out N_columns (as a subscript) or S_upper or L_dual or f_transform. This is also something I see more in CS papers than in non-CS math content.
1) A lot of frustration comes from bad expectations about how easy a math formulate should be to read. If I see 3 short lines of code, my gut tells me "this will be easy", and it's right. If I see 3 lines of math I feel like it should be easy but then get frustrated when 30 minutes later I'm still looking at the same 3 lines.
2) Once you understand a formula, I often decided I couldn't write it any better myself. It's most useful as a tool for thought and remembering, not necessarily as a tool for teaching.
The idea is to have equations (in LaTeX) and code (in PyTorch) line-by-line, so it is easy to see how to use it in practice.
I think it may help to bridge the gaps between coders (but not experienced in maths) and mathematicians (but with little experience in practical programming).
It is not. E.g. x ∈ ℕ ∧ x > 2 ∧ x < 5 ∧ x % 2 = 0 implies x = 4. This is not something pure functional languages can express directly. In math we make common use of relations, of which functions are a special case, but not the common one and certainly not the only one. But even when we do work with functions, a functional PL does not suffice. E.g. writing f(t) = t + 1 ∧ x ∈ ℕ ∧ f(x) = 3 is equivalent to writing x = 2. Also, we commonly employ objects that are not computable.
This is just one of the many mathy myths that plague the FP community. Yes, there are some similarities between FP and mathematical notation, but FP and imperative are much closer to one another than either is to mathematics.
>>> from z3 import Int, solve
>>> x = Int('x')
>>> solve([x > 2, x < 5, x % 2 == 0])
[x = 4]If anything, this seems to support the original claim.
> E.g. x ∈ ℕ ∧ x > 2 ∧ x < 5 ∧ x % 2 = 0 implies x = 4.
in Agda would be this, I think:
_ : ∀ { x : ℕ } → x > 2 → x < 5 → (x % 2) ≡ 0 → x ≡ 4It's as expressive.
> For example, Hoare Logic cant really deal with Higher-Order things.
1. It can. 2. It doesn't matter so much, as there are no higher order "things" but rather higher-order ways to describe things. For example, in mathematics higher-order systems can be described as either higher-order ODEs or equivalent first-order ODEs. In other words, "order" is a feature of the signifier, not the signified. For example, things that would be higher-order in Agda are first-order in TLA+ (and you don't need to go that far: formal set theories are usually first-order, yet you need higher-order typed logics to describe the same things).
> They do struggle with more "extensional" properties, such as function extensionality.
Well, that's because they're constructive. There are type-theory-based proof assistants that more easily support classical mathematics, like Lean.
Second, you can prove those equivalences in any language that allows you to directly express relations, be it the type-level language of Agda, Coq or F*, or the contract language of an imperative language -- this is nothing to do with FP, but with a language that can express relations.
sum i = 1 to 5 of i -> 1 + 2 + 3 + 4 + 5 = 15
Both can express and are equivalent to Turing machines.
That arbitrary mathematical proofs can be equivalently made by Turing machines (and conversely, that predicate calculus is Turing complete) is a lemma by Turing, published in the same 1936 paper in which he introduced the notion of computation, Turing machines and proved what today is known as the halting problem.
Many numerical algorithms for differential equations update a field in place. Sometimes you need to be very careful in your description of how something gets updated in order to avoid data conflicts. If you define it as a function then you have a single option if you want to do this "in place": sparse matrix representation of the updated values and a write of the updated values into the memory. As an example, memory requirements for line relaxation in multigrid can be done as an O(1) operation instead of as the O(n^1/d) operation of a sparse copy.
A mathematical function does not always return the same value. There are stochastic differential equations and random variables. For the sake of formality, they are frequently treated as discrete samples taken from a random distribution, but the naive approach of acting like the output of some function ε is random maps nicely into computers. If you are not "abusing notation" by using the functional notation, then the sample can be different every time you "take" it. Either way, you are not returning the same value each time.
It is useful to be able to describe certain mathematical operations as updates instead of as pure functions. Mathematics certainly isn't incapable of doing this. There is a lot of value in functional descriptions as well. If you are a purist on either side, you are just ignoring valuable things for the sake of your ideal.
I checked the RSS feed and couldn't find the article in it. I cross-checked the oldest article in the feed with the index of articles on the site, this article seems to be written before Dec 2014. This makes sense for why Julia isn't included.
This might be a good community project - the article on github and allow people to do pull requests adding their favorite language.
The first version is from Nov. 14: https://web.archive.org/web/20111114185849/http://matt.might... The article index from Nov. 8 does not include the article: https://web.archive.org/web/20111108003034/http://matt.might...
So we can say with confidence that this should have a [2011] tag and was published sometime Nov 8 - Nov 14 in 2011.
(I was reading another article from his site yesterday after it was linked on lobste.rs and was also trying to figure out how old it was.)
(Which they should do, it's useful)
https://crypto.stanford.edu/~blynn/haskell/ga.html
I am personally learning Shen[1] because Lisp, optional typing (great type system), and the formal work done within it, and for it in proving, verification and other related endeavors. It seems to tick the Haskell, Lisp, Prolog and logic boxes for me. Its portability is great[2], however, it is still young and building libraries. I am thinking on trying to mimic the DL work done by Dragan Djuric[3] for Clojure in Shen. We'll see how that goes...
[1] http://www.shenlanguage.org/ [2] https://shen-language.github.io/ [3] https://dragan.rocks/
I highly recommend reading [0], which contains the simplest (IMO) description of the simplex algorithm, which is both mathematical and executable. If you find that inspiring, [1] is also worth a read.
[0] https://www.jsoftware.com/papers/DFSP.htm
[1] http://www.eecg.toronto.edu/~jzhu/csc326/readings/iverson.pd...
Packages like this one are dope https://github.com/korsbo/Latexify.jl
Or this
https://github.com/qojulia/QuantumOptics.jl
Or this
"Many of the encodings are as immutable, purely functional data structures (even in imperative languages), a topic unfortunately omitted from many computer science curricula."
Julia and similar PLs don't express math like APL, J[1], Haskell[2], Scheme[3] or even Clojure can with immutable structures and function composition to name a couple. Sure you can write it in Julia, but I don't think the article is about creating math output in the Latexify.jl example, but how to code these math structures where certain languages can express them out of the box in an easier manner.
[1] https://www.jsoftware.com/books/pdf/
[2] https://www.amazon.com/Haskell-Logic-Programming-Second-Comp...
[3] https://mitpress.mit.edu/sites/default/files/titles/content/...
Primitive types (like pretty much all languages) are immutable and structs in Julia are immutable by default (which includes pretty much every math type like complex numbers), and all math operators are non mutating (in fact mutating operators should have a ! in the name).
Function composition is just as simple in this scenario:
f(x) = x + 2
g(x) = 2x
h = g ∘ f
h(3) == 10
Here is a simple example in J:
+/ % #
The above is an average function in J. It is a fork, where you fold right over the input (+/), and divde (%) by the tally (#) or count of items, so that
(+/ % #) 4.5 3 2 12
produces 5.375 as the average of the input vector. Notice the array-based language deals with singular quantities or scalars, vectors, and multi-dimensional arrays as fundamentals of the PL.
You could also define it as:
average =: +/ % #
for those who make the readability argument, however, you learn math symbols and read math papers full of them, and not lengthy verbal descriptions of these math formulas (average is equal to the "sum all of the input elements, and divde by the count or tally of input items").
The fact that a highly-functional APL program can fit on one screen negates the argument that you need readability, so that when you pick up or someone else picks up, your 110K lines of JavaScript code they can make a change. You may have to do a refresh read in APL and J, but because it is terse, you can deal it pretty quickly. Well-commented code in the 100k to 1 million lines of code scale will never allow one person to see the whole picture.
The work by Aaron Hsu in APL is amazing. Here is a link to the slides from a talk he gave. It's a bit lengthy but I found it very interesting and appropriate to this topic:
https://sway.office.com/b1pRwmzuGjqB30On
The YouTube link to the talk is here:
s = <s1, s2, ... sn> (Please note that in LaTeX, one should use \langle and \rangle for angle brackets--not less than and greater than.)
The article is pretty good overall, but I find this an little odd. I don't think I've ever seen sequences denoted with angle brackets. You usually see those used for denoting an inner product. I've only ever seen sequences denoted with parentheses, like (a_n) = (a_1, a_2, ..., a_n).
It's kind of humorous to me that we can sort of fingerprint the textbooks/lecturers people learned from by the idiosyncrasies of their notation.
It seems like this effort is going to increase a lot of overhead to do math, and obscures the role of thinking through the math conceptually. There seems to be a Principia Mathematica 2.0 idea in the programming world that we just need to reduce mathematics to code and it'll become easily accessible and usable. I'm not convinced that will be the case.
I didn't pick up any ideology in my reading. My interpretation of the article is that the author wanted to provide tips on how to implement mathematics, for two reasons:
1. People have to implement nontrivial mathematics from time to time, and
2. Most mathematics doesn't concern itself with obstacles to implementation, because it doesn't have to.
I am not sure what you mean by infinity here, but there are many ways in programming to handle infinite streams in an otherwise finite program. Python's itrrtools.count and the ability to map and filter over it would be a basic example.
Indeed I could argue that every game's or webserver's event loop is embedding infinity in a finite program.
I assume you have already proven we ourselves are an infinite computational mechanism?
For the purpose of constructing a generator, the author wrote:
> In an object-oriented setting like Python or Java, streams can be constructed from an interface
Yikes. itertools was introduced in, let's see... 2003?
def int_generator():
i = 0
while True:
yield i
i += 1
for n, square in ((i, i * i) for i in int_generator()):
print(f"{n}² = {square}")
time.sleep(1)