
Translating Mathematics into Code: Examples in Java, Python, Haskell and Racket - lelf
http://matt.might.net/articles/discrete-math-and-code/
======
j2kun
> Mathematics has no side effects.

I'm aware the author is a professor of CS, but this is a statement I always
see people originally trained as programmers claim, and as a mathematician and
a programmer I respectfully disagree.

Mathematics does what you define it to do, and if you can communicate your
idea to another person it doesn't matter whether you "mutated" a variable or
not. Likewise, you could say that there's no such thing as mutation in
programs because the value of a variable in a language that supports mutation
depends implicitly on time; you just don't express that in the source code.
It's a matter of perspective, and more perspectives are often better than
fewer. In math if you want to index a variable to have "pretend mutation" to
avoid confusion you can, but there's no rule about it. If you feel the best
way to communicate that idea is with mutation, then that doesn't stop it from
being mathematics.

~~~
jameshart
One obvious example of a mutable variable is in math's very own expression of
the for loop:

    
    
         n
        ∑  ƒ(i)
       i=m
    

This implies a mutating variable (i) and a hidden mutating accumulator that
tracks the sum. It seems like a perfectly clear mathematical expression of the
concept, though, in spite of the fact that it is fraught with 'unmathematical'
mutation.

I can think of many mathematical algorithms which, when stated most simply,
imply the mutation of state. Dijkstra's shortest path, for example, requires
you to label graph nodes with distances and states which change with each
iteration. You _can_ implement it, obviously, on purely functional data
structures, but doing so with mutable graph node structs isn't going to
undermine the validity of your implementation of what is at core an iterative
algorithm designed to be efficient in terms of the amount of additional data
you need to store to run it on a given graph.

~~~
tel
I disagree completely on both examples. The first I have a technical nitpick
to illustrate a deeper point and the second I have merely a stylistic point.

Firstly, I disagree completely that sum notation implies a hidden mutating
variable. The most obvious way to attack this point is to note that sum
notation is often applied when the summing domain is _infinite_ and therefore
if it means anything constructive (and it easily can!) then it certainly
cannot be interpreted as a mutable loop.

Instead, it's best to merely have it represent the well-defined notion of a
sum and note that it can be _interpreted_ in many ways. This interpretation
could involve using an algebraic identity (as one must with infinities) or, in
the exact case you have an ordered finite domain, be interpreted _either_ as a
mutating iterative summing algorithm _or_ a recursive immutable one.

The recursive bit applies exactly and only when the mutating algorithm one
does.

\---

As for Djikstra's algorithm, Djikstra wrote it using the popular computer
science notation of the time. Nobody denies that this formulation of the
algorithm requires mutation to implement, but it's merely a formulation of it
used for proof purposes. The idea of Djikstra's algorithm can be expressed
without using a mutable language---it's trivial at its basest, merely replace
mutation with a bunch of copies of your graph---and there's no particular
reason to prefer either one!

~~~
tel
As a further intensifying point, _this is why Djikstra spent so long making
sure he understood and communicating ALGOL and FORTRAN and the like so well_.
He wanted to explore new notations and needed to be absolutely clear how they
worked.

This is similarly why Milner, Tofte, Harper, MacQueen _completely specified_
the behavior of SML. [0]

[0] [http://www.amazon.com/The-Definition-Standard-ML-
Revised/dp/...](http://www.amazon.com/The-Definition-Standard-ML-
Revised/dp/0262631814)

------
brudgers
This:

    
    
        public Node(SortedSet<T> left, T element, SortedSet<T> right) {
          this.left = left ;
          this.right = right ;
          this.element = element ;
    

Isn't really mathematics. Nodes have a label. Any record attached to the node
is business logic. It doesn't matter if the tuple is (first, last, address,
department) or (value left, right), these are not part of the mathematics.
Sure (value, left, right) looks like math, but it's just a convenient place to
cache the edges describing a particular form of graph.

A graph is defined mathematically _G = {V, E}_. A single vertex with no edges
is a graph. A set of vertices with no edges is also a graph. These may or may
not be interesting, but edges are dependent on vertices. The converse is not
true.

This example with Node(value, left, right) is standard object oriented fair.
It's worse than Car(model, manufacturer, color, year). The Car simplifies
something complex. Node(value, left, right) makes something simple more
complicated. It's an implementation not an abstraction.

~~~
kyllo
The article seems to be not-so-subtly hinting that Java is an anti-math
programming language, and I agree. The language encourages each developer to
reinvent and reimplement key concepts in terms of "classes" that are much more
succinctly described in languages that embrace abstract algebra. The example
of using inheritance and dynamic dispatch to represent a union type, is a
perfect example.

~~~
Klockan
Union types is not a key concept in abstract algebra, I bet that most
mathematicians have never even heard of it. I'd like to hear about its use in
abstract algebra, how would you define the union type of the simplest of
simple objects without breaking its operation: a group with a group?

~~~
throwaway283719
That would be a _groupoid_ \-
[http://en.wikipedia.org/wiki/Groupoid](http://en.wikipedia.org/wiki/Groupoid)

~~~
Klockan
No, groupoids breaks the group operation and thus behaves like neither of the
groups. Do type systems allow operations between union types? If not then it
is just a simple interface in OO. If they do then you are no longer working
with pure functions.

------
Animats
The article doesn't mention matrices, which map to multidimensional arrays.
One of the basic features of FORTRAN, all the way back to the original version
for the IBM 704 in 1954, was multidimensional arrays. Yet C, C++, Go, and Rust
all lack them. They all have "arrays of arrays", or some hack involving macros
and templates and a multiply for every array access. (Yes, there's a sort of
multidimensional array capability in C99, but it is not used much.)

For Go and Rust, this subject has been discussed.[1][2] In both cases, the
participants in the discussion got tangled up with how slicing syntax would
interact with multidimensional arrays, and ended up doing nothing.

The number-crunching community is mostly using Matlab/Octave, and Python with
NumPy.

[1] [https://groups.google.com/forum/#!searchin/golang-
nuts/Multi...](https://groups.google.com/forum/#!searchin/golang-
nuts/Multidimensional$20array$20go/golang-nuts/WwQOuYJm_-s/pazcOKRyNz4J)

[2] [http://internals.rust-lang.org/t/difficulty-with-
rfc-439-and...](http://internals.rust-lang.org/t/difficulty-with-rfc-439-and-
multidimensional-arrays/1066)

------
strictnein
Maybe my brain isn't fully operational yet this morning, but I feel like this
is backwards:

> X ⊂ Y.

> This subset relationship could be represented as inheritence in a language
> like Java or Python, if these sets are meant to be types:

> class X extends Y { ... }

If X extends Y, then isn't X a superset of Y, not a subset? I feel like it
should be: class Y extends X { ... }

------
mrcactu5
Mathematical constructions can be difficult to interpret as code or visualize.
I have tried quite a few:

[http://monsieurcactus.github.io/circles/122514-Lima%C3%A7ons...](http://monsieurcactus.github.io/circles/122514-Lima%C3%A7ons.html)

------
Klockan
I wont believe in functional programming as long as not even mathematicians
prefer it.

