Translating Mathematics into Code: Examples in Java, Python, Haskell and Racket

http://matt.might.net/articles/discrete-math-and-code/

by lelf • 11 years ago

121 48 11 years ago

matt.might.net

mrcactu5• 11 years ago

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

j2kun7• 11 years ago

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.

meric• 11 years ago

> the value of a variable in a language that supports mutation depends implicitly on time

Mind blown.

platz• 11 years ago

Welcome to FRP

j2kun7• 11 years ago

What blows my mind is that variables in C implicitly depend not only on time but also on the entire contents of memory!

the_af4• 11 years ago

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.

But this is precisely the problem with mutation and programming languages:

    ...some code...
    y = f(x)
    ...more code...
    z = g(x)

Is x in the two lines the same? Often it's not. This is what's surprising to a mathematician. It would help if the "time" was made explicit, i.e. if you had x(t1) and x(t2), in which case it's quite obvious you need to take a closer look. But in mainstream imperative languages there is no support for this, which is very much a problem.

j2kun7• 11 years ago

I think what's surprising to a mathematician is if the fact that x can change is not stated prior to witnessing it. So you might say that immutability is a reasonable default for mathematics, but again not necessary as the author claims.

While I think programmers might find it surprising, in mathematical proofs context is often the primary tool one uses to figure out what the hell is going on locally in some expression. For example, indices like time and the size of a problem (in combinatorics) are often dropped because the reader understands that the context is asymptotic.

tel6• 11 years ago

I don't think anyone, mathematicians or functional programmers, have a problem with mutation [0]. They have a problem with names suddenly changing without being too explicit about that fact.

In particular, mathematics certainly doesn't prohibit you from using whatever kind of notation you like to explain your concept, but it has suggested a certain primacy of the notion of a (pure) function. The reasons are both ones of mathematical "elegance" (whatever that means) and pedagogy. They're a fantastically important fundamental building block.

Mathematicians would never claim that pure functions are the only thing around, but by and large they'd assume that's what you were talking about given no other indication. Furthermore if you introduced something new (say something with a notion of mutation) then you'd merely be obliged to explain exactly what that new thing is with sufficient formality so that the reader can be assured that its behavior is completely reasonable.

All of this holds identically for functional programming. The only additional challenge is that FPers are accidental intuitionists so you can't merely name the behavior of a new kind of notation but must actually exhibit an interpreter of that new notation into more common notation. This is significantly more heavy-handed than most mathematicians would do.

[0] Or any other side effects. The whole argument is parametric in your choice of side effect.

orbifold7• 11 years ago

From a mathematicians perspective, functional programming languages do a fairly bad job at being able to express algorithms in the way mathematicians have been writing them down since before computers existed. There is little difference between writing $x_{k+1} = f(x_{k})$ and $x = f(x)$ in an imperative language. In some cases the index k can even be identified as a multiplicator of some discrete timestep, in which case what the hardware is doing is in very close correspondence to the abstract iterative process.

All the operations in abstract algebra are actually destructive by default, if you do a multiplication, then that is a map

m : A \otimes A \to A

If you want a copy of the values you put in you have to pre- compose, with a diagonal map \Delta: A \to A \otimes A, which might even not exist (it doesn't if \otimes is the tensor product of vector spaces for example). Even application of a morphism on its own is treated as irreversible, once you've applied a morphism to an Object you can't get it back unless you are in a special category like Set, or the morphism happens to be invertible. The fact that functional programming languages hide copying behind your back does not make sense physically either, on a hardware level duplication is fairly expensive, because it decreases entropy.

There are countless examples in Computational Physics and Numerics, where pure functional programming languages fall flat on the nose. I'm thinking about finite-element methods with adaptive refinements, all the code for computer algebra and computational group theory, etc., not to mention all the Fortran/C/C++ code that is in existence in physics (At Cern they have written 60 million lines of it). It might be that the experts in functional programming languages simply don't have the expertise necessary to come up with viable solutions, because things like repa and accelerate are not realistic alternatives when it comes to real world applications.

Klockan4• 11 years ago

Java has no functions and is the language which gets harped on the most, so this is obviously not the main issue.

jameshart2• 11 years ago

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.

asuidyasiud4• 11 years ago

Mathematicians arguably do not think of the first example as a loop with a mutating variable, but rather as a short-hand notation for f(m) + ... + f(n) - as a macro, if you wish.

I agree with the second part.

the_af4• 11 years ago

Dijkstra's shortest path: good point. There is obviously a purely functional implementation, but it's true that the most natural way of thinking about it involves assigning labels.

I disagree about the sum "loop". It's merely a notation, not an actual step by step operation. Unlike a traditional imperative language's variable, i's value cannot be changed. Whatever the actual expression of f, you know i is always the same within it. You could think of it this way: "for each value v from range m..n, introduce a new variable i at each step with value v, which we will use for the expression".

tel6• 11 years ago

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!

j2kun7• 11 years ago

I actually agree with your example. The point is that nobody should care whether one interprets the looping variable (and underlying sum) as mutation or as shorthand for a mutationless expression. It's pretentious and counterproductive to call one interpretation mathematics and the other not.

agumonkey• 11 years ago

I always justify immutability by the fact that I like my assumptions not to change. I expect mathematicians to enjoy that property too.

ps : FP expresses changes as new instances with new parameters. Pushing away mutation as far as possible.

coldtea• 11 years ago

If you feel the best way to communicate that idea is with mutation, then that doesn't stop it from being mathematics.

No, but it does stop it from being mathematics as commonly taught, written and practiced in mathematical notation, which for all intents and purposes its the same.

That is, you're technically correct, which is the worst kind of correct.

brudgers• 11 years ago

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.

sukilot2• 11 years ago

Node isn't a graph here. Not sure what it is, at is like a "cut" but is rather underspecified. But it's not a bad model of... Whatever it is modeling.

j2kun7• 11 years ago

I think it's supposed to be a set, but as modeled by a red-black tree. So a graph, but not a general graph and with more metadata.

kyllo2• 11 years ago

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.

Klockan4• 11 years ago

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?

Animats• 11 years ago

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

[2] http://internals.rust-lang.org/t/difficulty-with-rfc-439-and...

Klockan4• 11 years ago

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

strictnein• 11 years ago

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 { ... }

Translating Mathematics into Code: Examples in Java, Python, Haskell and Racket

Related Stories