By the way, with this little program I have found two new compiler bugs, I will put it in Bugzilla later.

Bye,
bearophile

> with this little program I have found two new compiler bugs, I will put it in Bugzilla later.

http://d.puremagic.com/issues/show_bug.cgi?id=9520
http://d.puremagic.com/issues/show_bug.cgi?id=9521

Bye,
bearophile

The version you have put in Rosettacode is good, I have just added some missing tests at the beginning of the UTM constructor.

Annotations like this are reminders of DMD bugs/limits that hopefully we'll be fixed/lifeted:
foreach (/*const*/ s, const rule; aa) {


While this annotation:
alias State = char; // Typedef?

means that in a stronger typed entry maybe State should be (but we have also to benchmark if this doesn't decrease the program performance for a successive bigger Busy Beaver machine):
alias State = Typedef!char;


This little program is pedagogically very good at showing the difference between weak and strong static typing. In a strongly static typed version all (or most) of those run-time tests are not needed.

Bye,
bearophile

On 16-2-2013 18:23, bearophile wrote:
> The version you have put in Rosettacode is good, I have just added some missing tests at the beginning
>  of the UTM constructor.

I added that precondition reluctantly, that's why its short :-). I really feel that
input validation should be done elsewhere.

I was thinking about adding a factory method to the UTM that accepts a string array,
parses and validates it, and returns a fully initialized immutable TuringMachine.
It would still be a lot of ugly code though.

That stronger typing can reduce the need for input checking is something I find
interesting. I'll have a look at the Ada code.
 
> (but we have also to benchmark if this doesn't decrease the program performance for a
>  successive bigger Busy Beaver machine):

On the other hand, if we have stronger typing we may not have to do the rather expensive
checks that are currently in the loop.

Jos van Uden:

> I added that precondition reluctantly, that's why its short :-). I really feel that
> input validation should be done elsewhere.

A full validation needs to be done somewhere :-)


> I was thinking about adding a factory method to the UTM that accepts a string array,
> parses and validates it, and returns a fully initialized immutable TuringMachine.
> It would still be a lot of ugly code though.

Probably in D there are better solutions.



> That stronger typing can reduce the need for input checking is something I find interesting.

It's interesting :-) A strong typing has some disadvantages (the code is more fussy, the program usually gets a little less easy to read and a little longer, etc.), but it has some advantages too. Languages like Ada, Haskell and ATS enjoy such strong typing to avoid many bugs and many run-time errors.

In some Rosettacode Tasks I have put two different solutions, one less and one more strongly typed:

http://rosettacode.org/wiki/Hidato#D

http://rosettacode.org/wiki/Matrix_multiplication#D

There are languages like ATS (http://www.ats-lang.org/ ) able to catch statically many problems otherwise found at run-time in lesser languages. Well written ATS programs are also fast as C programs, so there is no loss in performance. On the other hand writing ATS code is not easy.


> I'll have a look at the Ada code.

Ada code is very readable (far more than C++). But compared to D you have to write too much code.


>> (but we have also to benchmark if this doesn't decrease the program performance for a
>> successive bigger Busy Beaver machine):
>
> On the other hand, if we have stronger typing we may not have to do the rather expensive
> checks that are currently in the loop.

Right :-)

Onward to the next Rosetta tasks :-)

Bye,
bearophile

There is a way to make the D code faster: prepending a cell in left() is a slow operation:

void right() pure nothrow {
    this.position++;
    if (this.position == this.tape.length)
        this.tape ~= this.blank;
}

void left() pure nothrow {
    if (this.position == 0)
        this.tape = this.blank ~ this.tape;
    else
        this.position--;
}


If you want to make the code faster (useful for a larger Busy Beaver simulation), you keep two tapes as two dynamic arrays. One tape represents the items on the right of the origin and the other tape on the left of the origin. So the position becomes a signed integer and both left() and right() use a fast append operation.

Bye,
bearophile

On 16-2-2013 19:55, bearophile wrote:
> There is a way to make the D code faster: prepending a cell in left() is a slow operation:
>
> void right() pure nothrow {
>      this.position++;
>      if (this.position == this.tape.length)
>          this.tape ~= this.blank;
> }
>
> void left() pure nothrow {
>      if (this.position == 0)
>          this.tape = this.blank ~ this.tape;
>      else
>          this.position--;
> }
>
>
> If you want to make the code faster (useful for a larger Busy Beaver simulation), you keep two tapes as two dynamic arrays. One tape represents the items on the right of the origin and the other tape on the left of the origin. So the position becomes a signed integer and both left() and right() use a fast append operation.

Yes, that was your original suggestion, but I didn't quite understand it,
so I went with the Ruby solution. You would reverse the left array when
printing, is that correct?

Jos van Uden:

> Yes, that was your original suggestion, but I didn't quite understand it,

When you don't understand something I say, please ask for more info :-)


> You would reverse the left array when printing, is that correct?

Right, the second half of the tape keeps the cells in reverse order.

Bye,
bearophile

On 16-2-2013 21:23, bearophile wrote:
> Jos van Uden:
>
>> Yes, that was your original suggestion, but I didn't quite understand it,
>
> When you don't understand something I say, please ask for more info :-)
>
>
>> You would reverse the left array when printing, is that correct?
>
> Right, the second half of the tape keeps the cells in reverse order.

I've split the tape in left and right. It does make the code a bit
harder to understand and debug. A linkedlist would have been more
elegant, but slower I guess.

The stress test that was posted on the talk page, I've also added.
Our UTM produces the correct result but with redundant blanks on
both sides.

0111111222222220
 ^

http://codepad.org/2SK611Wd

Jos van Uden:

> I've split the tape in left and right. It does make the code a bit harder to understand and debug.

You have used three tapes and a unsigned position, while I think a signed position and two tapes is enough:

static struct TapeHead {
    immutable Symbol blank;
    Symbol[] tape, left, right;
    size_t position;


The code becoming a little longer and a little less easy to understand was expected. But is it worth doing it for this Rosettacode Task? I think it's not worth making the code more complex.


With the tm3 the new code prints the last two states:

0111111222222220
 ^
0111111222222220
 ^


While the older code prints something different and probably more correct:

0111111222222220
^
0111111222222220
 ^


> A linkedlist would have been more elegant, but slower I guess.

On modern CPUs 99% of the times linked lists are the wrong data structure to use. They have low data density and incur in high cache misses. Benchmarks shows that in some cases arrays need to be preferred even when deletions in the middle are not so common.

Linked lists are better when you have to insert and remove many items randomly in the middle of the sequence and you don't have to transverse all the sequence often. This double condition is not so common.


> The stress test that was posted on the talk page, I've also added.

Good. It's better to add it to the precedent version of the UTM.


> Our UTM produces the correct result but with redundant blanks on
> both sides.
>
> 0111111222222220
>  ^

A Turning Machine is supposed to have a tape that is infinite in both directions, so when you print the tape you trim the blanks away at both ends.

So a better printing is:

...11111122222222...


Or:

Incrementer:
...111...
   ^
...111...
    ^
...111...
     ^
...1110...
      ^
...1111...
     ^

Bye,
bearophile