• Nathan M. Swan (15/15) Feb 17 2012 I'm working on a novice solver of the travelling salesman
• Timon Gehr (120/133) Feb 17 2012 Hi Nathan,

"Nathan M. Swan" <nathanmswan gmail.com> writes:

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

Timon Gehr <timon.gehr gmx.ch> writes:

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


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