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;