Translating Mathematics into Code: Examples in Java, Python, Haskell and Racket • Hacker News Board

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

#11

Post by j2kun » Tue, Feb 10, 2015, 3:02 AM UTC

meric wrote: post #5

j2kun wrote: post #4

> 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'…

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

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

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

#12

Post by brudgers » Tue, Feb 10, 2015, 3:07 AM UTC

This:

    public Node(SortedSet left, T element, SortedSet 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.

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

#13

Post by orbifold » Tue, Feb 10, 2015, 3:13 AM UTC

tel wrote: post #9

j2kun wrote: post #4

> 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'…

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…

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.

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

#14

Post by sukilot » Tue, Feb 10, 2015, 3:52 AM UTC

j2kun wrote: post #11

meric wrote: post #5

Earlier quoted context omitted.

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

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

And also depend on all the contents of disk and network and all attached input devices.

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

#15

Post by sukilot » Tue, Feb 10, 2015, 3:56 AM UTC

brudgers wrote: post #12

This: public Node(SortedSet left, T element, SortedSet 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 con…

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.

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

#16

Post by Animats » Tue, Feb 10, 2015, 4:05 AM UTC

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

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

#17

Post by tel » Tue, Feb 10, 2015, 4:23 AM UTC

sukilot wrote: post #14

j2kun wrote: post #11

Earlier quoted context omitted.

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

And also depend on all the contents of disk and network and all attached input devices.

And if things are multithreaded then shared memory variables depend implicitly upon all possible actions of all possible simultaneous threads.

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

#18

Post by j2kun » Tue, Feb 10, 2015, 4:27 AM UTC

sukilot wrote: post #15

brudgers wrote: post #12

This: public Node(SortedSet left, T element, SortedSet 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 con…

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.

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.

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

#19

Post by tel » Tue, Feb 10, 2015, 4:32 AM UTC

orbifold wrote: post #13

tel wrote: post #9

Earlier quoted context omitted.

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…

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…

I'm sadly not actually able to follow what you're getting at here.

I think there are a few threads going on that I'd be interested in following up on, whether imperative/mutable semantics are common in mathematics, whether it makes sense to call something in abstract algebra as "destructive", what copying means, whether analyzing computational physics/numerics is a similar task, whether functional programming experts are capable of building real world applied math tools...

Ultimately, though, I'm not sure which ones move the conversation along productively.

I think perhaps the most interesting one is the notion of copying. It is certainly the case that modern FP assumes copying is okay. This comes naturally from the "structural properties" of implication in type theory and there's plenty of work studying type theories which are "substructural" and thus don't assume an ambient copy/destroy comonoid. I don't honestly consider this out of scope of FP, although no languages implement it today. There is a need to pick a "default semantics sweet spot" and linear logic may have not yet proven it pays its way on the weight/power tradeoff spectrum. But maybe it will be shown to in time?

In the mean time you can do plenty of work in abstract algebra without talking about mutation or destruction at all. You mention category theory but ignore the prime dictum of CT: it's all about the arrows. Categories certainly exist which embody destructive internal algebras---CT would be pretty useless if it didn't---but externally we consider arrows and compositions of arrows alone. This is where the real power of CT comes from anyway.

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

#20

Post by jameshart » Tue, Feb 10, 2015, 5:26 AM UTC

j2kun wrote: post #4

> 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'…

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.