View mode: basic / threaded / horizontal-split · Log in · Help
August 18, 2012
CT Busy Beaver
On Reddit I have found a little C++11 program, here a little 
reformatted:
http://ideone.com/Vzkt8

The C++11 program implements a Turing machine at compile time, 
using two compile-time linked lists to represent each half of the 
tape (in such lists the ends handily loop on themselves). And 
then the Turing machine is programmed with a Busy Beaver.

So I have tried to port it to D, but it doesn't work yet, I have 
troubles with the template pattern matching (some programs 
related to this have given me optilink errors, but here the 
problem is different and larger):
http://dpaste.dzfl.pl/3195c63f

In this D version D I have kept the original structure, so I have 
not used two TypeTuples, also because of the loops at the list 
ends.

This D code is not going to be used for practical work. But do 
you know how to fix/improve it?

Bye, and thank you,
bearophile
August 18, 2012
Re: CT Busy Beaver
> But do you know how to fix/improve it?

Sorry, I have to give more info. I think the Turing machine and 
the Busy Beaver code work correctly. I think the problem is 
inside the "printing" function, that is the TypeListToArray, that 
converts a CT linked list to an array, that later is printable.

Bye,
bearophile
August 19, 2012
Re: CT Busy Beaver
On 08/18/2012 04:07 PM, bearophile wrote:
> On Reddit I have found a little C++11 program, here a little reformatted:
> http://ideone.com/Vzkt8
>
> The C++11 program implements a Turing machine at compile time, using two
> compile-time linked lists to represent each half of the tape (in such
> lists the ends handily loop on themselves). And then the Turing machine
> is programmed with a Busy Beaver.
>
> So I have tried to port it to D, but it doesn't work yet, I have
> troubles with the template pattern matching (some programs related to
> this have given me optilink errors, but here the problem is different
> and larger):
> http://dpaste.dzfl.pl/3195c63f
>
> In this D version D I have kept the original structure, so I have not
> used two TypeTuples, also because of the loops at the list ends.
>
> This D code is not going to be used for practical work. But do you know
> how to fix/improve it?
>
> Bye, and thank you,
> bearophile

Took me a while! Phew... :)

  http://dpaste.dzfl.pl/6b362382

I had lots of trouble matching the template specialization that I 
needed. And a million silly mistakes of mine. Anyway... Produces the 
same output.

Ali

-- 
D Programming Language Tutorial: http://ddili.org/ders/d.en/index.html
August 19, 2012
Re: CT Busy Beaver
Ali Çehreli:

> Took me a while! Phew... :)
>
>   http://dpaste.dzfl.pl/6b362382
>
> I had lots of trouble matching the template specialization that 
> I needed. And a million silly mistakes of mine. Anyway... 
> Produces the same output.

It's tricky code :-) But it's a nice exercise for C++11 template 
programming.

Most of your code is very similar to mine, but I can also see 
many little differences, so it seems you have written your 
translation from scratch.

In your code you have left the original C++11 naming conventions:
struct step(Direction d, Left, Right) {

But in D it's better to write:
struct Step(Direction d, left, right) {

In type_list_to_vector you have solved the problems in a simple 
way and using a quite different way.

Thank you,
bearophile
August 19, 2012
Re: CT Busy Beaver
Ali Çehreli:

> Took me a while! Phew... :)
>
>   http://dpaste.dzfl.pl/6b362382

I have back-ported your changes to my version, and it works (with 
few improvements, a larger Busy Beaver, etc):

http://dpaste.dzfl.pl/0791bea9

-----------------------

I have also tried to replace your code like this:

struct TypeListToArray(node : Cons!(value, tail), int value, 
tail) {
    void opCall(ref int[] output) {
        output ~= value;
        TypeListToArray!tail tl2v;
        tl2v(output);
    }

    static auto opCall() {
        TypeListToArray!node tl2v;
        return tl2v;
    }
}

struct TypeListToArray(node : Repeat!value, int value) {
    void opCall(ref int[] output) {
        output ~= value;
    }
}

import std.array;
void main() {
    import std.stdio;
    alias TuringMachine!(BusyBeaver2, Repeat!0, Repeat!0) tm;

    int[] tape1;
    TypeListToArray!(tm.finalLeft)()(tape1);
...


With a shorter template like:

template TypeListToArray(Node) {
    static if (is(Node Repeat : Repeat!value, int value))
        enum TypeListToArray = [value];

    static if (is(Node Cons : Cons!(value, Tail), int value, 
Tail))
        enum TypeListToArray = [value] ~ 
TypeListToArray!(Node.tail);
}

import std.array;
void main() {
    import std.stdio;
    alias TuringMachine!(BusyBeaver2, Repeat!0, Repeat!0) tm;

    enum tape1 = TypeListToArray!(tm.finalLeft);
...

But it's not working. Do you know why?

Bye,
bearophile
August 19, 2012
Re: CT Busy Beaver
> (some programs related to this have given me optilink errors,

In the latest version I've shown if you replace this in the 
larger Busy Beaver:

struct TransitionTable(int sym, state) {

With a template:

template TransitionTable(int sym, state) {

You get an optlink crash. I don't know if this is fit for 
Bugzilla.

Bye,
bearophile
August 19, 2012
Re: CT Busy Beaver
On Sunday, 19 August 2012 at 14:18:45 UTC, bearophile wrote:
> You get an optlink crash. I don't know if this is fit for 
> Bugzilla.

Any crashes should be submitted to Bugzilla, regardless of what 
input produced them. And besides that, the code presented here is 
actually quite short for a linker crash test case.

David
August 19, 2012
Re: CT Busy Beaver
On 08/19/2012 04:44 AM, bearophile wrote:

> Most of your code is very similar to mine, but I can also see many
> little differences, so it seems you have written your translation from
> scratch.

Yes, I've decided to start from scratch. I did look at yours after 
struggling for some time and I was surprised to see how much 
similarities there were between yours and mine.

Especially the 'static assert(false)' trick: Both you and I have thought 
about using. Those were helpful in solving the two linker errors (which 
maybe what you have experinced too).

The calls inside main() were being resolved to the D-equivalent of this 
struct template (I don't have the D-equivalent anymore):

template<typename T>
struct type_list_to_vector {
    void operator()(std::vector<int> &output);
};

And of course because there was no definition, the linker was 
complaining. I saw that only after implementing the above operator() as 
an opCall() that contained only a single 'static assert(false)'.

Then, I saw my mistake: The Head template parameter had to be 'int' (not 
type).

> In your code you have left the original C++11 naming conventions:
> struct step(Direction d, Left, Right) {
>
> But in D it's better to write:
> struct Step(Direction d, left, right) {

Absolutely. I've decided to make as little changes as needed.

> In type_list_to_vector you have solved the problems in a simple way and
> using a quite different way.

It is interesting and problematic that I could not replace the following 
two lines:

        type_list_to_vector!Tail tl2v;
        tl2v(output);

With the following line (which is closer to the C++11-original) even 
before or after defining a 'static opCall()':

        type_list_to_vector!Tail()(output);

Error: function 
deneme.type_list_to_vector!(repeat!(0)).type_list_to_vector.opCall (ref 
int[] output) is not callable using argument types ()

I thought that it was a bug that the compiler does not construct an 
object and call opCall() on it. (Note: I now suspect that the opCall() 
being non-const could be the problem; but I still could not make it work.)

> Thank you,
> bearophile

Thanks for the challenge,
Ali
August 19, 2012
Re: CT Busy Beaver
On 08/19/2012 07:07 AM, bearophile wrote:
> Ali Çehreli:
>
>> Took me a while! Phew... :)
>>
>> http://dpaste.dzfl.pl/6b362382
>
> I have back-ported your changes to my version, and it works (with few
> improvements, a larger Busy Beaver, etc):
>
> http://dpaste.dzfl.pl/0791bea9
>
> -----------------------
>
> I have also tried to replace your code like this:
>
> struct TypeListToArray(node : Cons!(value, tail), int value, tail) {
> void opCall(ref int[] output) {
> output ~= value;
> TypeListToArray!tail tl2v;
> tl2v(output);
> }
>
> static auto opCall() {
> TypeListToArray!node tl2v;
> return tl2v;
> }
> }
>
> struct TypeListToArray(node : Repeat!value, int value) {
> void opCall(ref int[] output) {
> output ~= value;
> }
> }
>
> import std.array;
> void main() {
> import std.stdio;
> alias TuringMachine!(BusyBeaver2, Repeat!0, Repeat!0) tm;
>
> int[] tape1;
> TypeListToArray!(tm.finalLeft)()(tape1);
> ...
>
>
> With a shorter template like:
>
> template TypeListToArray(Node) {
> static if (is(Node Repeat : Repeat!value, int value))
> enum TypeListToArray = [value];
>
> static if (is(Node Cons : Cons!(value, Tail), int value, Tail))
> enum TypeListToArray = [value] ~ TypeListToArray!(Node.tail);
> }
>
> import std.array;
> void main() {
> import std.stdio;
> alias TuringMachine!(BusyBeaver2, Repeat!0, Repeat!0) tm;
>
> enum tape1 = TypeListToArray!(tm.finalLeft);
> ...
>
> But it's not working. Do you know why?

Here is a reduced code:

template Foo(T)
{
    static if (is (T : int)) {
        enum Foo = [ T.init, T.init ];

    }

    static if (is (T : long)) {
        enum Foo = [ T.init ];

    }
}

void main()
{
    enum i = Foo!int;
    enum l = Foo!long;
}

Error: template instance deneme.Foo!(int) error instantiating

Works if the two 'static if' blocks are connected with an else:

    static if (is (T : int)) {
        enum Foo = [ T.init, T.init ];

    } else static if (is (T : long)) {  // <-- else makes it compile
        enum Foo = [ T.init ];
    }

>
> Bye,
> bearophile

Ali
August 20, 2012
Re: CT Busy Beaver
Ali Çehreli:

> I thought that it was a bug that the compiler does not 
> construct an object and call opCall() on it.

In the D front-end there are some well known bugs regarding 
opCall (and I think there is a patch too).



> Works if the two 'static if' blocks are connected with an else:
>
>     static if (is (T : int)) {
>         enum Foo = [ T.init, T.init ];
>
>     } else static if (is (T : long)) {  // <-- else makes it 
> compile
>         enum Foo = [ T.init ];
>     }

I think the problem is different:
http://dpaste.dzfl.pl/86bcd51a

Bye,
bearophile
Top | Discussion index | About this forum | D home