Hacker News Reader

Comment by jameshart | Hacker News Reader

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.

View on HN

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!

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

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

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.

Right - my point was more in the context of the idea that to correctly translate that mathematical concept to code you are doing it wrong if you use mutation. If a mathematical algorithm you're implementing contains a summation, you're not fundamentally misrepresenting the underlying mathematical purity if you implement it as a for loop with an accumulator.

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.

Reply on news.ycombinator.com