Immutability, problems with debugging

[Timon Gehr]

On 02/17/2012 11:51 AM, Nathan M. Swan wrote:
> I'm working on a novice solver of the travelling salesman problem, and
> when I decided to go concurrent I had to make everything immutable. Now
> this happens:
>
> /usr/share/dmd/src/phobos/std/format.d(1782): Error: function
> object.Object.toString () is not callable using argument types () immutable
>
> Unfortunately, I don't know how format is called, so I can't investigate
> closer. Does anyone notice anything glaringly obvious?
>
> https://github.com/carlor/tsp.d/blob/master/tsp.d
>
> This brings up an issue that's happened before; there's an error in the
> semantics of a (usually generic) function call, and I don't know where
> the function is called. It would be nice if the compiler could do
> something like "mentioned on file1.d(33), mentioned on file2.d(107)".
>
> Thanks, NMS

Hi Nathan,

This kind of question usually is better placed in d.D.learn.
Anyway, the reason why your code does not work is because 
std.concurrency cannot yet deal with head-immutable data. (It will work 
as soon as these issues are fixed.) I have edited the code to a point 
where it compiles. (probably is also more efficient than before.) I hope 
I have preserved the semantics.

What version of the compiler are you using? I didn't get the error you 
describe.


/* tsp.d - a multithreading implementation of the traveling salesman problem
Copyright (C) 2012 Nathan M. Swan
See README for details.

tsp.d is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

tsp.d is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Foobar. If not, see <http://www.gnu.org/licenses/>.
*/
module tsp;

import std.algorithm;
import std.array;
import std.concurrency;
import std.conv;
import std.exception;
import std.functional;
import std.math;
import std.stdio;

void main(string[] args) {
     try {
         enforce(args.length == 2, "must give city file");
         auto cities = readFromFile(args[1]);
         auto route = bestRouteBetween(cities[0], cities[0],
                                                  cities[1 .. $]);
         writeln("Distance: ", route.distance);
         foreach(city; route.cities) {
	        writeln(city.name);
         }
     } catch (Exception e) {
         stderr.writeln("Error: ", e.msg);
     }
}

immutable(City)[] readFromFile(string fname) {
	immutable(City)[] r;
     foreach(line; File(fname, "r").byLine()) {
         // get rid of comments
         line = findSplit(line, "#")[0];

         // put into three tokens
         auto tkrange = splitter(line, " ");
         string[] tokens = filterEmpties(tkrange);

         if (tokens.length == 0) continue;

         // construct city
         enforce(tokens.length == 3, "must be three tokens per line");
         r~=City(tokens[0],to!real(tokens[1]),to!real(tokens[2]));
     }
     return r;
}

// return the best route between the two cities containing the others
Route bestRouteBetweenFunc(City a,
                            City b,
                            immutable(City)[] others)
{
     if (others.length) {
         Route best = Route([], real.max);
         foreach(i, o; others) {
	        spawn(&brtWrapper, thisTid, b, i, cast()o, others);
         }
         foreach(i; 0 .. others.length) {
	        Route r = receiveOnly!(Route)();
             auto realdist = r.distance + distanceBetween(a, others[i]);
             if (realdist < best.distance) {
                 best = Route(a ~ r.cities, realdist);
             }
         }
         return best;
     } else {
         return Route([a, b], distanceBetween(a, b));
     }
}

// calls the bestRouteBetween function and notifies
void brtWrapper(Tid parent, // thread to alert of being done
                 City b, // the last chain member
                 size_t i, // index of o
                 City o, // o, the focused chain member
                 immutable(City)[] others) // the non-b chain members
{
     auto r = bestRouteBetween(o, b, others[0..i] ~ others[(i+1)..$]);
     parent.send(r);
}

real distanceBetweenFunc(City a, City b) {
     real xs = a.x - b.x;
     real ys = a.y - b.y;
     return sqrt(xs*xs + ys*ys);
}


string[] filterEmpties(T)(T range) {
     string[] r;
     foreach(str; range) {
         if (!str.empty) {
             r ~= str.idup;
         }
     }
     return r;
}

struct City {
     string name;
     real x;
     real y;
}

struct Route {
	this(immutable(City)[] c, real d) { cities = c; distance = d; }

	immutable(City)[] cities;
     real distance;
}

alias memoize!bestRouteBetweenFunc bestRouteBetween;
alias memoize!distanceBetweenFunc distanceBetween;