Hello,

I came back to D after a longer break and just wanted to set up a small project to further get in contact with this language.

However, it seems that the codes which simply shall simulate a deterministic finit automaton do not work correctly.

CODE ---

struct DeterministicState {
public:
	this(string name, bool isFinal, DeterministicState[char] transits...) {
		this.name = name;
		this.finalState = isFinal;
		this.addTransits(transits);
	}

	this(string name, bool isFinal) {
		this.name = name;
		this.finalState = isFinal;
	}

	this(bool isFinal, DeterministicState[char] transits...) {
		this("", isFinal, transits);
	}

	this(DeterministicState[char] transits...) {
		this("", false, transits);
	}

	void addTransits(DeterministicState[char] newTransits) {
		foreach (immutable key; newTransits.keys) {
			transits[key] = newTransits[key];
		}
	}

	string getName() const {
		return name;
	}

	bool isFinalState() const {
		return finalState;
	}

	bool hasNext(char input) const {
		return (input in transits) ? true : false;
	}

	DeterministicState getNext(char input) {
		return transits[input];
	}

	string toString() const {
		return name;
	}

private:
	string name;
	DeterministicState[char] transits;
	bool finalState;
}

struct DeterministicFiniteAutomaton {
public:
	DeterministicState[] input(char[] input) {
		DeterministicState[] trace = [ start ];
		auto currentState = trace[0];
		foreach (immutable c; input) {
			if (currentState.hasNext(c) == false) {
				writeln(currentState.toString() ~ " has next for " ~ to!string(c));
				break;
			} else {
				writeln(currentState.toString() ~ " has NO next for " ~ to!string(c));
			}
			currentState = currentState.getNext(c);
			trace ~= currentState;
		}
		return trace;
	}

	this(DeterministicState start) {
		this.start = start;
	}

private:
	DeterministicState start;
}

void main()
{
	auto s0 = DeterministicState("s0", false);
	auto s1 = DeterministicState("s1", false);
	auto s2 = DeterministicState("s2", true);
	s0.addTransits(['0' : s1, '1' : s2]);
	s1.addTransits(['0' : s0, '1' : s2]);
	s2.addTransits(['0' : s2, '1' : s2]);
	auto dfa = DeterministicFiniteAutomaton(s0);
	auto trace = dfa.input("0001".dup);
	foreach (t; trace) {
		writeln(t.toString());
	}
	writeln("Trace Length = " ~ to!string(trace.length));
}

---

The output is the following:

s0 has NO next for 0
s1 has next for 0
s0
s1
Trace Length = 2

Which states that the trace for input "0001" has just a length of 2 instead of 4. And I do not really understand why s1 has no next item while it was defined in main.

I hope someone can clear things up for me. I really don't get why this isn't working as intended.

Regards,
Rob

On 09/16/2014 09:08 PM, Robin wrote:

> struct DeterministicState {

Structs are value types. When they are copied, the mutations that you expect may be happening on a copy.

I don't understand what exactly should happen but the following changes produce at least a different output. :)

1) Change the 'struct' above to 'class':

class DeterministicState {

2) Use the 'override' keyword with toString:

     override string toString() const {

3) Create the objects with new:

    auto s0 = new DeterministicState("s0", false);
    auto s1 = new DeterministicState("s1", false);
    auto s2 = new DeterministicState("s2", true);

Here is the output after that.

s0 has NO next for 0
s1 has NO next for 0
s0 has NO next for 0
s1 has NO next for 1
s0
s1
s0
s1
s2
Trace Length = 5

4) Also, the following conditional seems backward to me:

>              if (currentState.hasNext(c) == false) {
>                  writeln(currentState.toString() ~ " has next for " ~
> to!string(c));

Should it not be simply 'if (currentState.hasNext(c))'?

Ali

Hiho,

thank you for your response on my topic.

However, I still do not understand why it didn't work for struct value types since I do not perform any mutations on the state objects during execution of the code.

The only thing happening with them is that they are getting copied bitwise and thus should have the same entries in the associative array as the original source, or am I wrong with this?

When value types are copied bitwise then the associative array should also be copied that way or at least point to the same mapping as the source and thus shouldn't be empty after copying.

What changes are required in order to make it work with struct value types as well? I even tried to change getNext to work with pointer return values instead but that did not help either.

Regards,
Rob

On 09/17/2014 03:42 AM, Robin wrote:> Hiho,

> However, I still do not understand why it didn't work for struct value
> types since I do not perform any mutations on the state objects during
> execution of the code.

I was a little sloppy with my response. :) What I suspected is still correct though. The following are the mutations:

    s0.addTransits(['0' : s1, '1' : s2]);
    s1.addTransits(['0' : s0, '1' : s2]);
    s2.addTransits(['0' : s2, '1' : s2]);

Note that s0 gets a copy of s1 before s1 knows about its transits.

> When value types are copied bitwise then the associative array should
> also be copied that way or at least point to the same mapping as the
> source and thus shouldn't be empty after copying.

There is an issue with uninitialized associative arrays: Although one would think that both s1 copies would use the same AA, since the AA is uninitialized, they would both initialize it first, having separate AAs.

This is a pretty nasty problem as it matters whether the AA had a single record before the copy or not. :(

> What changes are required in order to make it work with struct value
> types as well?

I am ashamed to admit that I am not sure how to initialize an AA to the empty state. I can do the following though: :)

        this.transits['z'] = this;
        this.transits.remove('z');

Ali

Hiho,

thank you for your response!

You just showed me my flaws while programming with value types. I think the only close solution is to work with pointers to the created states within the associative array instead of direct value types.

Thanks for clearing this up to me. =)

Regards,
Rob

Here is the fully working code for everyone experiencing similar bugs or problems with pointers and value types. =)

struct DeterministicState {
public:
	this(string name, bool isFinal, DeterministicState *[char] transits...) {
		this.name = name;
		this.finalState = isFinal;
		this.addTransits(transits);
	}

	this(string name, bool isFinal) {
		this.name = name;
		this.finalState = isFinal;
	}

	this(bool isFinal, DeterministicState *[char] transits...) {
		this("", isFinal, transits);
	}

	this(DeterministicState *[char] transits...) {
		this("", false, transits);
	}

	void addTransits(DeterministicState *[char] newTransits) {
		foreach (immutable key; newTransits.keys) {
			transits[key] = newTransits[key];
		}
	}

	string getName() const {
		return name;
	}

	bool isFinalState() const {
		return finalState;
	}

	bool hasNext(char input) const {
		return (input in transits) ? true : false;
	}

	DeterministicState * getNext(char input) {
		return transits[input];
	}

	string toString() const {
		return name;
	}

private:
	string name;
	DeterministicState *[char] transits;
	bool finalState;
}

struct DeterministicFiniteAutomaton {
public:
	DeterministicState *[] input(char[] input) {
		DeterministicState *[] trace = [ start ];
		auto currentState = trace[0];
		foreach (immutable c; input) {
			if (!currentState.hasNext(c)) {
				writeln(currentState.toString() ~ " has no next for " ~ to!string(c));
				break;
			} else {
				writeln(currentState.toString() ~ " has next for " ~ to!string(c));
			}
			currentState = currentState.getNext(c);
			trace ~= currentState;
		}
		return trace;
	}

	this(DeterministicState * start) {
		this.start = start;
	}

private:
	DeterministicState * start;
}

void main()
{
	auto s0 = DeterministicState("s0", false);
	auto s1 = DeterministicState("s1", false);
	auto s2 = DeterministicState("s2", true);
	s0.addTransits(['0' : & s1, '1' : & s2]);
	s1.addTransits(['0' : & s0, '1' : & s2]);
	s2.addTransits(['0' : & s2, '1' : & s2]);
	auto dfa = DeterministicFiniteAutomaton(& s0);
	auto trace = dfa.input("0001".dup);
	foreach (t; trace) {
		writeln(t.toString());
	}
	writeln("Trace Length = " ~ to!string(trace.length));
}

Regards,
Rob

On Wednesday, 17 September 2014 at 21:33:01 UTC, Robin wrote:
> Here is the fully working code for everyone experiencing similar bugs or problems with pointers and value types. =)
>
> struct DeterministicState {
> public:
> 	this(string name, bool isFinal, DeterministicState *[char] transits...) {
> 		this.name = name;
> 		this.finalState = isFinal;
> 		this.addTransits(transits);
> 	}
>
> 	this(string name, bool isFinal) {
> 		this.name = name;
> 		this.finalState = isFinal;
> 	}
>
> 	this(bool isFinal, DeterministicState *[char] transits...) {
> 		this("", isFinal, transits);
> 	}
>
> 	this(DeterministicState *[char] transits...) {
> 		this("", false, transits);
> 	}
>
> 	void addTransits(DeterministicState *[char] newTransits) {
> 		foreach (immutable key; newTransits.keys) {
> 			transits[key] = newTransits[key];
> 		}
> 	}
>
> 	string getName() const {
> 		return name;
> 	}
>
> 	bool isFinalState() const {
> 		return finalState;
> 	}
>
> 	bool hasNext(char input) const {
> 		return (input in transits) ? true : false;
> 	}
>
> 	DeterministicState * getNext(char input) {
> 		return transits[input];
> 	}
>
> 	string toString() const {
> 		return name;
> 	}
>
> private:
> 	string name;
> 	DeterministicState *[char] transits;
> 	bool finalState;
> }
>
> struct DeterministicFiniteAutomaton {
> public:
> 	DeterministicState *[] input(char[] input) {
> 		DeterministicState *[] trace = [ start ];
> 		auto currentState = trace[0];
> 		foreach (immutable c; input) {
> 			if (!currentState.hasNext(c)) {
> 				writeln(currentState.toString() ~ " has no next for " ~ to!string(c));
> 				break;
> 			} else {
> 				writeln(currentState.toString() ~ " has next for " ~ to!string(c));
> 			}
> 			currentState = currentState.getNext(c);
> 			trace ~= currentState;
> 		}
> 		return trace;
> 	}
>
> 	this(DeterministicState * start) {
> 		this.start = start;
> 	}
>
> private:
> 	DeterministicState * start;
> }
>
> void main()
> {
> 	auto s0 = DeterministicState("s0", false);
> 	auto s1 = DeterministicState("s1", false);
> 	auto s2 = DeterministicState("s2", true);
> 	s0.addTransits(['0' : & s1, '1' : & s2]);
> 	s1.addTransits(['0' : & s0, '1' : & s2]);
> 	s2.addTransits(['0' : & s2, '1' : & s2]);
> 	auto dfa = DeterministicFiniteAutomaton(& s0);
> 	auto trace = dfa.input("0001".dup);
> 	foreach (t; trace) {
> 		writeln(t.toString());
> 	}
> 	writeln("Trace Length = " ~ to!string(trace.length));
> }
>
> Regards,
> Rob

Out of curiosity, why did you decide to stick with structs
instead of simply using classes?  To avoid heap allocations?

This is actually a good question as this code isn't really complex or doesn't require the best possible performance.
But in case I will ever need optimum performance I should have learned how to handle tasks with value types which is the main reason why I chose them instead of reference types - for learning purposes.

- can't hurt! ;)

Regards,
Rob

On Wednesday, 17 September 2014 at 21:45:01 UTC, Robin wrote:
> This is actually a good question as this code isn't really complex or doesn't require the best possible performance.
> But in case I will ever need optimum performance I should have learned how to handle tasks with value types which is the main reason why I chose them instead of reference types - for learning purposes.
>
> - can't hurt! ;)
>
> Regards,
> Rob

Probably also has applicability when creating compile-time data
structures that have scope-limited lifetimes.