www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - CT Busy Beaver

reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Aug 18 2012
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 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
Aug 18 2012
prev sibling next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Aug 18 2012
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Aug 19 2012
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Aug 19 2012
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Aug 19 2012
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Aug 19 2012
parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Aug 20 2012
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
 (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
Aug 19 2012
parent "David Nadlinger" <see klickverbot.at> writes:
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
Aug 19 2012