6 ms·

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

by j2kun 12y 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 12y ago
>> the value of a variable in a language that supports mutation depends implicitly on time Mind blown.
- platz 12y ago
  Welcome to FRP
- j2kun 12y ago
  What blows my mind is that variables in C implicitly depend not only on time but also on the entire contents of memory!
  - sukilot 12y ago
    And also depend on all the contents of disk and network and all attached input devices.
    - tel 12y ago
      And if things are multithreaded then shared memory variables depend implicitly upon all possible actions of all possible simultaneous threads.
the_af 12y 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.
- j2kun 12y 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.
  - the_af 12y ago
    > I think what's surprising to a mathematician is if the fact that x can change is not stated prior to witnessing it This is precisely what happens in languages without immutability / control of mutation. They effectively say "this may or may not mutate. See for yourself. Oops! It just mutated. Sorry!" Also, isn't what you talk about in your example just a shorthand to avoid cluttering a proof or whatever? It's not that variables mutate; it's that by convention you elide the notation that shows they mutate. That makes a lot of sense: the writer and the reader assume some things and go on with a compact notation that eliminates noise. It's a useful convention, and if the reader loses track of the notation, the worst that can happen is that he/she won't be able to understand the proof. The problem with computer programs is that it's about both the reader and the computer interpreting the program. Because variables may or may not mutate, it's harder for the computer to perform some optimizations. Because of the same reason, it's harder for humans to understand the code ("is this going to use the convention that it won't mutate variables? I have to carefully read the code and consider all paths in order to be sure"). In a sense, programming with uncontrolled mutation is like switching the default convention to its most confusing setting :)
tel 12y 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.
- orbifold 12y 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.
jameshart 12y 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.
- asuidyasiud 12y 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_af 12y 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".
- tel 12y 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!
agumonkey 12y 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 12y 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.

by j2kun 12y ago

meric 12y ago

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

platz 12y ago
Welcome to FRP
j2kun 12y ago
What blows my mind is that variables in C implicitly depend not only on time but also on the entire contents of memory!
- sukilot 12y ago
  And also depend on all the contents of disk and network and all attached input devices.
  - tel 12y ago
    And if things are multithreaded then shared memory variables depend implicitly upon all possible actions of all possible simultaneous threads.

the_af 12y 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.

j2kun 12y 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.
- the_af 12y ago
  > I think what's surprising to a mathematician is if the fact that x can change is not stated prior to witnessing it This is precisely what happens in languages without immutability / control of mutation. They effectively say "this may or may not mutate. See for yourself. Oops! It just mutated. Sorry!" Also, isn't what you talk about in your example just a shorthand to avoid cluttering a proof or whatever? It's not that variables mutate; it's that by convention you elide the notation that shows they mutate. That makes a lot of sense: the writer and the reader assume some things and go on with a compact notation that eliminates noise. It's a useful convention, and if the reader loses track of the notation, the worst that can happen is that he/she won't be able to understand the proof. The problem with computer programs is that it's about both the reader and the computer interpreting the program. Because variables may or may not mutate, it's harder for the computer to perform some optimizations. Because of the same reason, it's harder for humans to understand the code ("is this going to use the convention that it won't mutate variables? I have to carefully read the code and consider all paths in order to be sure"). In a sense, programming with uncontrolled mutation is like switching the default convention to its most confusing setting :)

tel 12y 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.

orbifold 12y 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.

jameshart 12y 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.

asuidyasiud 12y 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_af 12y 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".
tel 12y 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!

agumonkey 12y 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 12y 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.