Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Implementing a two-way Turing Machine tape as an improvement to std::deque |
| Date | 2022-05-13 02:38 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <8735he1abh.fsf@bsb.me.uk> (permalink) |
| References | <cNWdnXqV1cXzEuD_nZ2dnUU7_8zNnZ2d@giganews.com> <87wneq1ejm.fsf@bsb.me.uk> <MeOdncpeZacPMeD_nZ2dnUU7_8zNnZ2d@giganews.com> |
olcott <NoOne@NoWhere.com> writes:
> On 5/12/2022 7:06 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> I've removed the philosophy group and comp.lang.c as this is C++.
>>
>>> C/C++ people please critique this as the basis for an improvement to
>>> std::deque.
>> You will get critiques of the code on whatever basis people feel
>> inclined to comment! You can't limit the comments to some particular
>> context.
>>
>>> It seems to have the key functionality of std::deque and
>>> does it much more simply while saving time and space.
>> It does not have any of the functionality of std::deque.
>
> That is a ridiculously stupid thing to say. It has the key most
> important functionality of a std:deque
Generally, when you think I am saying something absurd, you should
re-consider.
A deque has (at least) these operations:
front
back
pop_front
push_front
pop_back
push_back
Your Tape_Type has none of these. Even internally it does not maintain
the right data to be able to provide them.
> Double ended queue
> deque (usually pronounced like "deck") is an irregular acronym of
> double-ended queue. Double-ended queues are sequence containers with
> dynamic sizes that can be expanded or contracted on both ends (either
> its front or its back).
>
> All of the rest of the functionality of std::deque can be added as
> needed.
You mean you could implement a deque using two arrays if you chose to?
So what? All I am saying is that you haven't got a deque.
>> There is a
>> commonly used (though not particularly efficient) way to implement a
>> deque using two arrays, but this is not it.
>>
>>> #define tape_element unsigned char
>> Use a typedef or using declaration. Also, I'd put the typedef in the
>> class as the type belongs to the class (as least that appears to be the
>> case from the name you've chosen).
>>
>>> class Tape_Type
>>> {
>>> private:
>>> int Tape_Head = 0; // Can be negative
>>> std::vector<tape_element> Left; // Stores left expansion
>>> std::vector<tape_element> Right; // Stores right expansion
>>> tape_element & operator[](int index);
>>>
>>> public:
>>> void move_left(); // Tape_Head--; Left.push_back(0); as needed
>>> void move_right(); // Tape_Head++; Left.push_back(0); as needed
>> The comments are wrong since you push_back('_').
>>
>>> void Write(tape_element Y){ this->operator[](Tape_Head) = Y; };
>>> tape_element Read() { return this->operator[](Tape_Head); };
>> I'd write (*this)[Tape_Head] but I suppose that's just a matter of style.
>>
>>> Tape_Type(){ Right.push_back('_'); } // constructor
>> The constructor leaves a Tape_Type object in an unusable state, but
>> that's due to a bug in operator[]. Did you test?
>
> Yes I tested so I don't see what you mean.
Testing should have caught the bug in operator[].
>>> void Output();
>>> };
>>>
>>> tape_element& Tape_Type::operator[](int index)
>>> {
>>> if (index > 0)
>>> return Right[index];
>> Bug. You meant index >= 0 I think.
>
> Yes Richard caught that. That was a new refactoring.
>>
>>> int Left_Index = ((index * -1) -1);
>> Why not -index - 1?
>>
>>> return Left[Left_Index];
>> Do you think introducing a new variable really make the code clearer
>> that simply writing
>> return Left[-index - 1];
>> ? Personally, I'd write the whole thing as
>> return index >= 0 ? Right[index] : Left[-index - 1];
>>
>>> }
>>>
>>> void Tape_Type::Output()
>>> {
>>> printf("Tape_Type::Output()\n");
>>>
>>> if (Left.size())
>>> {
>>> int Last_One = Left.size() - 1;
>>> for (int N = Last_One; N >= 0; N--)
>>> {
>>> int TH = (N + 1) * -1; // determine Tape_Head from N
>>> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
>>> }
>>> }
>>> if (Right.size())
>>> for (int N = 0; N < Right.size(); N++)
>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
>>> }
>>>
>>> void Tape_Type::move_left()
>>> {
>>> Tape_Head--;
>>> int Left_Index = ((Tape_Head * -1) -1);
>>> if (Left_Index == Left.size())
>>> Left.push_back('_');
>>> }
>>>
>>> void Tape_Type::move_right()
>>> {
>>> Tape_Head++;
>>> if (Tape_Head == Right.size())
>>> Right.push_back('_');
>>> }
>>
>> I find the capitalisation odd and unhelpful as there does not seem to be
>> any consistency about it.
>
> I found all of your suggestions very helpful.
> I don't see the bug in the constructor.
There is none. I just said the constructor leaves the tape unusable
because of the bug in operator[].
> I like mixed case because it is easier to read, mine not be consistent.
>
> Here they are implemented.
>
> //
> // Tape_Type implements a two-way Turing machine tape.
> // Right contains Tape_Head >= 0 values (right expansion)
> // Left contains Tape_Head < 0 values (left expansion)
> //
> // Tape_Type has functionality very similar to std::deque
This comment is not correct.
> // yet implements this functionality much more simply.
> // This saves time and space.
> //
> class Tape_Type
> {
> typedef unsigned char tape_element;
You probably want that to be a public typedef. And now that it's in the
class, the name can be sorter. The usual convention is _t for types:
typedef unsigned char element_t;
I plugged your tape class into my C++ TM interpreter and it made it
slightly slower for the "big" BB(5) test compared with my naive tape
that just uses a single string.
Note: this is not a comment on the design of your tape. There's nothing
wrong with it (except a little inconvenience, see below). The speed
will be determined almost entirely by how std::string and std::vector
are implemented. You might see completely different timings just by
linking with a different library.
Mind you, I prefer using a string to all the other methods I've tried
because it's so convenient. You can set up the TM with an input simply
by writing
tape = input
and you can debug by printing the tape any time you like. And I use a
string_view to get the non-blank "result" out of the TM and the end of a
run. All easy to get round with a couple of functions, but still, since
it's fast I see no reason t change.
--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 17:51 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-12 23:56 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:09 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:22 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:38 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:40 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:49 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 00:53 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 19:12 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 01:58 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 20:34 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 08:02 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque tth <tth@none.invalid> - 2022-05-13 09:10 +0200
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 10:58 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 17:02 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-05-13 12:44 -0700
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Richard Damon <Richard@Damon-Family.org> - 2022-05-12 19:23 -0400
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 18:32 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 01:06 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 19:55 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 02:01 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 20:36 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 08:04 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 11:00 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Mr Flibble <flibble@reddwarf.jmc> - 2022-05-13 17:04 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 12:05 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 02:38 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-12 21:37 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Python <python@example.invalid> - 2022-05-13 04:39 +0200
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 12:01 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 10:41 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Richard Damon <Richard@Damon-Family.org> - 2022-05-13 11:56 -0400
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 17:35 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 12:12 -0500
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque Ben <ben.usenet@bsb.me.uk> - 2022-05-13 20:04 +0100
Re: Implementing a two-way Turing Machine tape as an improvement to std::deque olcott <NoOne@NoWhere.com> - 2022-05-13 14:19 -0500
csiph-web