On 5/12/2022 8:38 PM, Ben wrote:
> 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
> push_front
> push_back
> pop_front
> pop_back
>
> Your Tape_Type has none of these. Even internally it does not maintain
> the right data to be able to provide them.

I also added a reserve so you could do a pre-allocated speed test.

It was easy to add these in terms of the current implementation:

public:
tape_element& front( ) { return Left.back(); }
tape_element& back() { return Right.back(); }
void pop_front() { Left.pop_back(); }
void pop_back() { Right.pop_back(); }
void push_front(tape_element& E) { Left.push_back(E); }
void push_back(tape_element& E) { Right.push_back(E); }

void reserve(unsigned int N)
{ Left.reserve(N); Right.reserve(N); }

>> 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.

If I added these things then I would have a much better 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[].

It is was a new refactoring of existing working code.

>>>> 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[].

Oh, OK.

>
>> 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.
>

std::string or char * ?
If char * was pre-allocated that would give it a big speed advantage.

I could add reserve(left/right):
void reserve(unsigned int N)
{ Left.reserve(N); Right.reserve(N); }

> 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.
>

What about memory allocation?

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer