Live data from Hacker News

Translating math into code with examples in Java, Racket, Haskell, Python (2011)

matt.might.net

81–90 of 95 posts

Re: Translating math into code with examples in Java, Racket, Haskell, Python (2011)

#81
post #28

> Mathematics is a purely functional language. It is not. E.g. x ∈ ℕ ∧ x > 2 ∧ x 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.

I also found this sidetrack to be a bit of a straw man. A large proportion of physics is devoted to dynamics: the study of change. There are mathematical descriptions for dynamics whereby a thing is updated x ↦ x + v * dt, v ↦ v + a * dt. You can think of a classical particle's position both as a thing that gets updated and as a function of time (time is definitely updating whether you like it and model it or not).

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.

Re: Translating math into code with examples in Java, Racket, Haskell, Python (2011)

#82

Earlier quoted context omitted.

Can you provide an example of mutability in, say, high school or undergraduate math?

any sum with an index of summation requires mutability

I don't think so. For example, sum of first 5 integers:

    sum i = 1 to 5 of i -> 1 + 2 + 3 + 4 + 5 = 15
Nothing mutable there. In functional programming this is done with a `fold`, which doesn't use mutation.

Re: Translating math into code with examples in Java, Racket, Haskell, Python (2011)

#83
post #29

Not sure what the point of translating math into code is. Just because we represent something with code doesn't mean it is computable. It's also technically incorrect to say math is translated into code. The mathematical symbols are being swapped with codey things, but the underlying semantics are quite different. For example, we might say the symbol 'oo' is infinity, but infinity itself is something that cannot be e…

>infinity itself is something that cannot be embedded in a finite program 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.

What you are describing is a potential infinity. I'm talking about an actual infinity.

Re: Translating math into code with examples in Java, Racket, Haskell, Python (2011)

#84
post #29

Not sure what the point of translating math into code is. Just because we represent something with code doesn't mean it is computable. It's also technically incorrect to say math is translated into code. The mathematical symbols are being swapped with codey things, but the underlying semantics are quite different. For example, we might say the symbol 'oo' is infinity, but infinity itself is something that cannot be e…

>> completely inaccessible to finite computational mechanisms. I assume you have already proven we ourselves are an infinite computational mechanism?

We can imagine infinity and its implications. E.g. what is the largest number? After thinking about it a bit, we realize there is no such thing. In that sense, we are not like finite computational devices. A computer cannot make the same kind of inference. It has to have the answer given to it.

Re: Translating math into code with examples in Java, Racket, Haskell, Python (2011)

#85
post #29

Not sure what the point of translating math into code is. Just because we represent something with code doesn't mean it is computable. It's also technically incorrect to say math is translated into code. The mathematical symbols are being swapped with codey things, but the underlying semantics are quite different. For example, we might say the symbol 'oo' is infinity, but infinity itself is something that cannot be e…

You and I read the article very differently. Based on your comment, it sounds like you interpreted the article as implicit advocation for the idea that mathematics should be represented in a programmatic (i.e. computable) way. 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 imple…

That's true, and numerical analysis can be quite helpful for mathematical insight. However, I've never found the math to code part to be tricky. It's mostly an after thought compared to the conceptualization itself. So the emphasis on coding math suggests a reversal of priorities. In my experience, focusing on the coding part becomes very inefficient, especially with combinatorial problems. No matter how tricky I get with the implementation, a combinatorial explosion is still a combinatorial explosion. Coming up with a neat analytic solution ends up being super efficient in comparison.

Re: Translating math into code with examples in Java, Racket, Haskell, Python (2011)

#86
post #18

Earlier quoted context omitted.

Agreed, i'm not sure whether one letter (immutable) greek variables are better than proper named variables. Another consideration: A formal rule based math syntax could be checked by a computer (theorem prover).

Where widely understood, I consider a Greek variable to be vastly superior. The problem is how well it's understood. Delta is an example of a succinct variable which has a well defined meaning which to encapsulate in a named variable either requires a long name or leaving out some nuance (delta isn't 'change' which is ambiguous in English, but the difference between two measurable things.) Keep in mind we use special…

It think this is somewhat similar to: many chinese characters vs ASCII. Neither is the superior notation. I prefer to write words by concatenation of multiple ASCII letters instead of one letter symbols, but that's due to my cultural background.

Re: Translating math into code with examples in Java, Racket, Haskell, Python (2011)

#87
post #33
post #13

Earlier quoted context omitted.

I like Julia for all of the libraries, the Lisp underneath, however, from the article: "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…

Can you explain it better? I do agree with Haskell due to laziness by default and arrow types for example, but against Scheme and Clojure the only aspect seels like it would be the more strict rebinding/shadowing rules (which doesn't limit what you can express, just that you can also express non-mathematical expressions). Primitive types (like pretty much all languages) are immutable and structs in Julia are immutabl…

@ddragon your points are well taken. I will look further into Julia. I still think when I wrote "out of the box" with APL in mind as far as expressing math, or J for that matter if you learn the ASCII symbols. I've seen other examples since your post on Julia that show similar math expressiveness, but they seem to rely on libraries or the syntactic sugar provided by the libraries. I haven't tried your example, but it looks like vanilla Julia. My familiarity with Matlab makes Julia an easy choice for me too.

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:

https://www.youtube.com/watch?v=9xCJ3BCIudI

Re: Translating math into code with examples in Java, Racket, Haskell, Python (2011)

#88
post #73

Earlier quoted context omitted.

An example of > E.g. x ∈ ℕ ∧ x > 2 ∧ x in Agda would be this, I think: _ : ∀ { x : ℕ } → x > 2 → x

The type level of dependently typed languages or other languages that allow directly expressing relations (including Java's JML) can do that. That's little to do with pure FP.

In some sense it does though. Type Theories (and their associated pure FP languages) often have the exact same algebraic structure as different classes of logic. To my understanding, JML uses Hoare Logic, which is a great tool for proving correctness of imperative languages, but is not quite as expressive. For example, Hoare Logic cant really deal with Higher-Order things. That's not to say Coq/Agda are perfect though. They do struggle with more "extensional" properties, such as function extensionality.

Re: Translating math into code with examples in Java, Racket, Haskell, Python (2011)

#89

Earlier quoted context omitted.

any sum with an index of summation requires mutability

I don't think so. For example, sum of first 5 integers: sum i = 1 to 5 of i -> 1 + 2 + 3 + 4 + 5 = 15 Nothing mutable there. In functional programming this is done with a `fold`, which doesn't use mutation.

We're talking about notation. Anything could be described in any Turing complete language. It's uncommon to have something similar to mutation in ordinary mathematical notation, but summation is one example where it's used.

Re: Translating math into code with examples in Java, Racket, Haskell, Python (2011)

#90
post #73

Earlier quoted context omitted.

The type level of dependently typed languages or other languages that allow directly expressing relations (including Java's JML) can do that. That's little to do with pure FP.

In some sense it does though. Type Theories (and their associated pure FP languages) often have the exact same algebraic structure as different classes of logic. To my understanding, JML uses Hoare Logic, which is a great tool for proving correctness of imperative languages, but is not quite as expressive. For example, Hoare Logic cant really deal with Higher-Order things. That's not to say Coq/Agda are perfect thoug…

> but is not quite as expressive

It'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.

Post reply on HN