Friday, December 2, 2016

Digest for comp.lang.c++@googlegroups.com - 25 updates in 5 topics

Ramine <ramine@1.1>: Dec 02 02:48PM -0500

Hello...........
 
About functional programming and object oriented programming..
 
I have continued to read about Lisp and Haskel functional languages,
and i have finally understood functional programming, in Lisp and
Haskel the functions are pure , that means that they don't call
global variables, but when you want to do mutability, you have
,like in message passing, to pass the local variable to an Mvar
in Haskel, it's like a queue, where the other threads must grap
this local variable and copy it in a local variable and
change it and put back this local variable in the queue for the other
threads to change it, so you will avoid race conditions in parallel
programming with this mechanism, but Mvar or the queues are still prone
to Deadlock or starvation. I have learned Lisp and Haskel and i have
noticed that to avoid the readability problem that i have spook about in
my previous post you have to decompose the many brackets with the defun.
 
In object oriented programming you can implement the Mvar of Haskel with
queues and you can avoid the problem of race conditions.
 
 
Thank you,
Amine Moulay Ramdane.
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 02 07:54PM

On 02/12/2016 19:48, Ramine wrote:
> queues and you can avoid the problem of race conditions.
 
> Thank you,
> Amine Moulay Ramdane.
 
Maybe someone should e-mail abuse@eternal-september.org to try and get
this spambot turned off?
 
/Flibble
Ramine <ramine@1.1>: Dec 02 02:58PM -0500

On 12/2/2016 2:54 PM, Mr Flibble wrote:
 
> Maybe someone should e-mail abuse@eternal-september.org to try and get
> this spambot turned off?
 
> /Flibble
 
Sorry, i have spook about object oriented programming like in C++ ,
and how to avoid race conditions.
 
Thank you,
Amine Moulay Ramdane.
Ramine <ramine@1.1>: Dec 02 03:03PM -0500

On 12/2/2016 2:54 PM, Mr Flibble wrote:
 
> Maybe someone should e-mail abuse@eternal-september.org to try and get
> this spambot turned off?
 
> /Flibble
 
Don't be stupid Flibble, i have explained to you what is good in Lisp
and Haskek an how to implement in C++ the Mvar like in Haskel to make
your C++ methods pure like in Lisp and use like a message passing
mechanism with queues to avoid race conditions like in Lisp and
Haskel.
 
 
Thank you,
Amine Moulay Ramdane.,
Ramine <ramine@1.1>: Dec 02 03:03PM -0500

On 12/2/2016 2:54 PM, Mr Flibble wrote:
 
> Maybe someone should e-mail abuse@eternal-september.org to try and get
> this spambot turned off?
 
> /Flibble
 
Don't be stupid Flibble, i have explained to you what is good in Lisp
and Haskek an how to implement in C++ the Mvar like in Haskel to make
your C++ methods pure like in Lisp and use like a message passing
mechanism with queues to avoid race conditions like in Lisp and
Haskel.
 
 
Thank you,
Amine Moulay Ramdane.,
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Dec 02 08:12PM

On Fri, 2 Dec 2016 19:54:15 +0000
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
[snip]
> Maybe someone should e-mail abuse@eternal-september.org to try and
> get this spambot turned off?
 
Out of the blue, my usenet provider has started blacklisting him in
recent weeks (I hadn't realised until you started replying to him, I
assumed he was taking a break from it). Eternal september seem to be
one of the few who are still OK with being used for spamming.
bleachbot <bleachbot@httrack.com>: Dec 02 08:48PM +0100

bleachbot <bleachbot@httrack.com>: Dec 02 08:56PM +0100

bleachbot <bleachbot@httrack.com>: Dec 02 08:58PM +0100

bleachbot <bleachbot@httrack.com>: Dec 02 09:03PM +0100

bleachbot <bleachbot@httrack.com>: Dec 02 09:03PM +0100

Ramine <ramine@1.1>: Dec 02 02:56PM -0500

Hello..........
 
About functional programming and object oriented programming..
 
I have continued to read about Lisp and Haskel functional languages,
and i have finally understood functional programming, in Lisp and
Haskel the functions are pure , that means that they don't use or call
global variables, but when you want to do mutability, you have
,like in message passing, to pass the local variable to an Mvar
in Haskel, it's like a queue, where the other threads must grap
this local variable and copy it in a local variable and
change it and put back this local variable in the queue for the other
threads to change it, so you will avoid race conditions in parallel
programming with this mechanism, but Mvar or the queues are still prone
to Deadlock or starvation. I have learned Lisp and Haskel and i have
noticed that to avoid the readability problem that i have spook about in
my previous post you have to decompose the many brackets with the defun.
 
In object oriented programming you can implement the Mvar of Haskel with
queues and you can avoid this way the problem of race conditions.
 
 
Thank you,
Amine Moulay Ramdane.
xerofoify <xerofoify@gmail.com>: Dec 02 10:14AM -0800

I am trying to write a linked list quicksort that works by only swapping the Nodes and was wondering why the below code does not work as I can't see why:
//Swap function for nodes
154 void swap ( Node* a, Node* b )
155 { Node t = *a; *a = *b; *b = t; }
156 //Partion function for nodes
157 Node* partition(Node *l, Node *h)
158 {
159 T x = h->data_;
160
161 Node *i = l->prev_;
162 for (Node *j = l; j != h; j = j->next_) {
163 if (j->data_ <= x) {
164 i = (i == nullptr)? l : i->next_;
165 swap(i, j);
166 }
167 }
168 i = (i == nullptr)? l : i->next_;
169 swap(i, h);
170 return i;
171 }
172 /*this does qsort recursively on the elements from the Node at the first iterator passed up to
173 and including the Node at iterator two*/
174 void qSortrecursive(iterator first, iterator second) {
175 Node* h = first.getNode();
176 Node* l = second.getNode();
177 if (h != NULL && l != h && l != h->next_)
178 {
179 struct Node *p = partition(l, h);
180 qSortrecursive(l, p->prev_);
181 qSortrecursive(p->next_, h);
182 }
183 }
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 02 07:17PM

On 02/12/2016 18:14, xerofoify wrote:
> 181 qSortrecursive(p->next_, h);
> 182 }
> 183 }
 
AFAIK quicksort will not work with linked lists; try merge sort instead.
 
/Flibble
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 02 12:32AM +0100

On 01.12.2016 22:34, Richard wrote:
> for methods and functions here feels gratuitous. It doesn't add any
> clarity but comes at the expense of more tokens I have to scan through
> in order to see what is happening.
 
There are no deduced return types in this code.
 
Mainly because I mostly agree with your sentiment here. :)
 
 
[snip]
> Slavishly using auto and trailing return types on functions/methods
> (and not even consistently throughout) just takes something simple
> and makes it more complicated without any benefit.
 
Re consistency, this code is totally consistent:
 
* `void` for Pascal /procedures/ (no expression result functions).
* `auto` for Pascal functions (functions that return value).
 
:)
 
But the 100% consistency here is just a coincidence, due to the
shortness of the code. I do not believe 100% consistency is good! In the
end, I believe, this boils down to the reason why programming can't be
automated: we need humans to supply intelligence.
 
Dang, there was a good quote about consistency, I've forgotten it...
 
 
Cheers!,
 
- Alf
legalize+jeeves@mail.xmission.com (Richard): Dec 01 11:57PM

[Please do not mail me a copy of your followup]
 
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> spake the secret code
>> [...] but the use of auto deduced return types
>> for methods and functions here feels gratuitous.
 
>There are no deduced return types in this code.
 
OK, consider that nit picked. s/deduced/trailing/.
 
>Re consistency, this code is totally consistent:
 
>* `void` for Pascal /procedures/ (no expression result functions).
>* `auto` for Pascal functions (functions that return value).
 
Again, back to the point of the audience that is reading this code.
The fact that you had to explain your "consistency" is buttressing my
assertion that this style is leading to less clarity and not more.
 
When I read the code, I see some things using trailing return types
and some things not using trailing return types.
 
If using auto is good enough for trailing type int, why isn't it
good enough for trailing type void?
 
If using classic return type without auto is good enough for void,
why isn't it good enough for int?
 
Etc.
 
Again, this style just makes me think "someone is all excited about
the new syntax of trailing return types and is using it gratuitously"
instead of using it where it adds clarity as in type deduction of a
return type from an expression using types of input arguments.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 02 01:14AM +0100

On 02.12.2016 00:57, Richard wrote:
>>> for methods and functions here feels gratuitous.
 
>> There are no deduced return types in this code.
 
> OK, consider that nit picked. s/deduced/trailing/.
 
There is world of difference.
 
 
> and some things not using trailing return types.
 
> If using auto is good enough for trailing type int, why isn't it
> good enough for trailing type void?
 
For the very common single case of `void` functions, `auto` just adds
verbosity (for member function implementations it can drastically reduce
verbosity, but for simple `void` functions it adds wordage).
 
Also, as I see it it's very nice to have this class of functions singled
out visually, as with the Pascal keyword `procedure` (which had that
exact purpose: to single them out). Because in the basic meaning the
`void` functions have a very different purpose, namely to /do/ something
rather than /compute/ something. Of course it's possible to use either
class of function for the opposite purpose, with just more awkward
notation, but that's the basis – and via the C++11 and later support for
move semantics, C++ now increasingly supports the style where
computations yield function results, used in /expressions/.
 
Most computer scientist, I believe, view that usage as the ideal, that a
routine that computes something should return that as its function
result, and therefore agree that the C conflation of procedure and
function was a bad choice. In original C one would have to let those
procedures return `int`, either explicitly or via C implicit int. It was
ugly, the code saying something different than the intention.
 
 
> If using classic return type without auto is good enough for void,
> why isn't it good enough for int?
 
Singling out `void`, procedures, is doable and has a reason (which IMO
is strong and good).
 
Not so for `int`.
 
But people have argued that `int main()` is so idiomatic that it just
feels wrong and perplexing to see it expressed with `auto`. I do that
for consistency. And also, to introduce the syntax to more people. :)
 
Cheers!,
 
- Alf
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 02 03:15AM +0100

On 01.12.2016 21:23, Mr Flibble wrote:
> On 01/12/2016 09:32, Alf P. Steinbach wrote:
[snip]
>> }
>> *p_ptr = new Node{ nullptr, nullptr, value };
>> }
 
[snip]
 
> Without balancing your tree is as good as useless; your post was totally
> pointless.
 
The intention of a "part 1", implying a later "part 2", and so on, was
to establish a baseline and see if the idea of generating discussion,
rather than providing it, panned out.
 
I agree that balancing is crucial for dealing with sorted or mostly
sorted input, to avoid quadratic accumulated insertion time.
 
And there's one even more special case to consider: the case of a sorted
input that is a sequence of equal values. Here simple balancing doesn't
help, because a sequence of equal values always becomes a degenerate
tree, a single branch of right-pointers (or left-pointers, depending on
one's choice), that cannot be balanced up. So ideally, to avoid square
time also for this special case, the `add` routine should be modified to
not descend down such a chain of equal value nodes.
 
Possibilities include:
 
• Inserting a new node with value V at the very top of an existing chain
of V, reducing the insertion complexity to logarithmic.
 
• Adding a value count in each node, and just incrementing it.
This precludes using the tree to associate different info with each
key V.
 
• Treating the tree as a simple set, and failing or doing nothing if V
already exists.
 
I think there may be some complexity hidden in the first possibility.
 
But anyway, as you can see, avoiding square time /in general/ so as to
make the structure generally useful, involves a decision about what the
tree is used for, and modifying the `add` routine accordingly:
 
a set (last bullet), a multiset (middle bullet), or a multimap (first
bullet)?
 
Cheers!,
 
- Alf
Daniel <danielaparker@gmail.com>: Dec 01 08:12PM -0800

On Thursday, December 1, 2016 at 6:35:48 PM UTC-5, Alf P. Steinbach wrote:
 
> Dang, there was a good quote about consistency, I've forgotten it...
 
One of these?
 
"A foolish consistency is the hobgoblin of little minds"
 
- Ralph Waldo Emerson
 
"Do I contradict myself? Very well, then I contradict myself, I am large, I contain multitudes."
 
- Walt Whitman
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 02 05:53AM +0100

On 02.12.2016 05:12, Daniel wrote:
 
> - Ralph Waldo Emerson
 
> "Do I contradict myself? Very well, then I contradict myself, I am large, I contain multitudes."
 
> - Walt Whitman
 
 
Yep. Thanks!
 
Cheers!,
 
- Alf
leigh.v.johnston@googlemail.com: Dec 02 05:45AM -0800

Adding multiple identical keys should be no problem for any self balancing search tree otherwise we wouldn't have std::multiset and std::multimap.
 
/leigh
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 02 03:32PM

On 02/12/2016 02:15, Alf P. Steinbach wrote:
 
> a set (last bullet), a multiset (middle bullet), or a multimap (first
> bullet)?
 
> Cheers!,
 
Perhaps you are talking about guaranteeing the stability of a sequence
of duplicate keys? In which case an incrementing counter approach will
mean your insert operation cannot guarantee logarithmic complexity any
longer. The correct approach to implementing a binary search tree that
guarantees stability of duplicate key order is to make it a hybrid data
structure that also includes a linked list: this approach offers other
advantages: iterator increment/decrement changes from logarithmic
complexity to constant time.
 
/Flibble
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 02 03:55PM

On 02/12/2016 02:15, Alf P. Steinbach wrote:
> tree is used for, and modifying the `add` routine accordingly:
 
> a set (last bullet), a multiset (middle bullet), or a multimap (first
> bullet)?
 
You are wrong about how multiset and multimap differ: certainly they do
not correspond to your bullet points. multiset and multimap have
identical data structures: the only difference is multimap value_type is
a pair in which the key is the first part.
 
/Flibble
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 02 04:15PM

On 02/12/2016 15:32, Mr Flibble wrote:
> structure that also includes a linked list: this approach offers other
> advantages: iterator increment/decrement changes from logarithmic
> complexity to constant time.
 
Obviously if you have a balancing scheme that does not alter sort order
of nodes (e.g. red-black tree rotation that most std:: node based
container implementations use) then stability of equivalent keys and
logarithmic complexity for insert can be guaranteed.
 
/Flibble
"Öö Tiib" <ootiib@hot.ee>: Dec 02 08:30AM -0800

> Adding multiple identical keys should be no problem for any self
> balancing search tree otherwise we wouldn't have std::multiset
> and std::multimap.
 
Not a problem but it takes some time to write and to test
otherwise we wouldn't have container templates.
There are different requirements so the underlying
implementation of such templates is often rather different.
Compare things like std::(unordered_)(multi)map(set,
boost::flat_(multi)map/set and boost::intrusive::set.
Lot of those don't even have tree underneath.
 
Implementing threaded binary tree sounds like not bad
idea as it allows to optimize out parent_ pointer in tree
node; fastens iterating over container up and reduces
potential need for recursive algorithms or fat iterators.
However that is theory ... in practice it looks like a
complex beast and so I haven't profiled one.
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)