EmbeddedRelated.com
Forums
The 2024 Embedded Online Conference

Digression on Iterators

Started by Jon Kirwan October 18, 2011
On Sun, 17 Jun 2012 22:09:03 +0200, you wrote:

>On 17/06/12 21:05, Jon Kirwan wrote:
>> On Sun, 17 Jun 2012 08:40:47 +0100, you wrote:
>>
>> > Have to say, I really don't like references in C or C++ code
>> > (or even XC code for that matter) but they are
>> > matter-of-fact in Pascal-class languages (derived from
>> > Algol's ref type).
>>
>> I would use references because they permit a compiler to do
>> better optimizations. They simply do. Of course, that doesn't
>> mean the compiler author will do anything useful with that
>> fact. But they could.
>>
>> Others might use them because they allow a quick-hack way of
>> suddenly turning a "by value" parameter into something they
>> can reach through and modify, breaking to earlier contract.
>> Maybe that is your problem. But it's not mine. I care about
>> better optimizations. A hope that has been repeatedly dashed
>> over and over again, by what I see as regression rather than
>> progress in that area. Supported by a few recent comments
>> lately here in this group by you, if I recall.
>>
>> Jon
>>I don't think references give the compiler much more opportunity for
>optimisations than pointers do. There are a few cases - it can be
>better for alias analysis, the compiler can assume they are non-zero,
>they can't change, etc. But for the most part, references are syntactic
>sugar for pointers.
>
>However, I think they are often nicer than pointers because it allows
>the benefits of pointers (such as avoiding copying large items by value)
>without many of the risks (the compiler can check that the reference is
>valid and non-zero at compile time), and with a cleaner and neater
>syntax. Cleaner source code and better static error checking is the
>winning point for me - better optimisations is a nice bonus.

Stroustrup says he first considered the idea of references
BECAUSE of the optimizations permitted when references are
used as parameters instead of pointers. A reference cannot be
changed during the function lifetime. It also cannot be 0. A
pointer can be changed and it can be 0. Static optimization
is much easier when you can know unambiguously what bit of
memory a variable means. Pointers break this condition.

That's part of what I remember.

Jon

Beginning Microcontrollers with the MSP430

On 17 Jun 2012, at 21:17, Jon Kirwan wrote:

> On Sun, 17 Jun 2012 22:09:03 +0200, you wrote:
>
>> On 17/06/12 21:05, Jon Kirwan wrote:
>>> On Sun, 17 Jun 2012 08:40:47 +0100, you wrote:
>>>
>>>> Have to say, I really don't like references in C or C++ code
>>>> (or even XC code for that matter) but they are
>>>> matter-of-fact in Pascal-class languages (derived from
>>>> Algol's ref type).
>>>
>>> I would use references because they permit a compiler to do
>>> better optimizations. They simply do. Of course, that doesn't
>>> mean the compiler author will do anything useful with that
>>> fact. But they could.
>>>
>>> Others might use them because they allow a quick-hack way of
>>> suddenly turning a "by value" parameter into something they
>>> can reach through and modify, breaking to earlier contract.
>>> Maybe that is your problem. But it's not mine. I care about
>>> better optimizations. A hope that has been repeatedly dashed
>>> over and over again, by what I see as regression rather than
>>> progress in that area. Supported by a few recent comments
>>> lately here in this group by you, if I recall.
>>>
>>> Jon
>>> I don't think references give the compiler much more opportunity for
>> optimisations than pointers do. There are a few cases - it can be
>> better for alias analysis, the compiler can assume they are non-zero,
>> they can't change, etc. But for the most part, references are syntactic
>> sugar for pointers.
>>
>> However, I think they are often nicer than pointers because it allows
>> the benefits of pointers (such as avoiding copying large items by value)
>> without many of the risks (the compiler can check that the reference is
>> valid and non-zero at compile time), and with a cleaner and neater
>> syntax. Cleaner source code and better static error checking is the
>> winning point for me - better optimisations is a nice bonus.
>
> Stroustrup says he first considered the idea of references
> BECAUSE of the optimizations permitted when references are
> used as parameters instead of pointers.

This might be for an era where compilers were typically weak and would not do what they currently do when disambiguating.

> A reference cannot be
> changed during the function lifetime. It also cannot be 0. A
> pointer can be changed and it can be 0.

Indeed, but if you do not alter the pointer in a function then a reference and a pointer are equivalent. A compiler can know a pointer is never assigned to and can simply ignore (or cause the computer to blow up) when assigning through zero.

> Static optimization
> is much easier when you can know unambiguously what bit of
> memory a variable means. Pointers break this condition.

I would disagree with this. You (typically) don't know where a reference points, you only know that it points "somewhere"; this is no different from knowing that a pointer points "somewhere". Assignment through a reference may change *anything* and a compiler will kill everything that it knows about (based on type) when assigning through a reference. It has no choice in the matter. You would have to provide a concrete example of how a compiler can do a better job using references than using pointers. I just do not see it.

I see absolutely no difference (speaking of absolutes) in the disambiguation process between assignment through a pointer and assignment through a reference and what the compiler must invalidate. But I am open to be corrected.

-- Paul.

On 17 Jun 2012, at 21:09, Jon Kirwan wrote:

> On Sun, 17 Jun 2012 18:10:26 +0200, David wrote:
>
>> On 17/06/12 02:00, Jon Kirwan wrote:
>>> On Sat, 16 Jun 2012 23:11:29 +0200, you wrote:
>>>
>>>> I am not sure if noexcept will negate all the bad points about
>>>> exceptions
>>>
>>> I never speak in absolutes -- except when saying that I
>>> absolutely don't do so. :)
>>>
>>
>> And I /always/ speak in absolutes - well, most of the time :-)
>
> Oh, cripes. I've been using iterator concepts and lazy
> evaluation for decades with good results. These are subsets
> of lambda calculus, as I'm learning more now.

Are you late to lambda calculus? Surely not. :-) lambda expressions are bread and butter to a Lisp programmer.

If you like thinking lambdas, you might like to get hold of a copy of this:



This is quite old, but it does a good job and expands the mind. Might be a bit out of date these days, as the comment says Mine is pristine. :-)

> But it is a
> VERY POWERFUL concept. One I've been using for almost two
> decades already because they work so well and improve the
> quality of the resulting code. If you are interested in
> seeing a good example, I'd be happy to show you how why they
> helped me recently and allow you to consider the alternative
> options to see why this is the better way to handle what I
> faced.
>
> And they are NOT AT ALL hard to follow!! The C++11 syntax is
> the ugliest, most vile way of specifying them I can imagine.
> It's despicable. But that is syntax, not semantics.
> Semantically, they are a thing of beauty and simplicity
> itself. Anyone can get the idea. Anyone. I just spent a few
> days doing a code review to programmers who'd never been so
> much as even exposed to the concept, let alone the syntax.
> And they came away wondering out loud why they'd never
> bothered to learn about it before.
>
> It took me 5 minutes to get the idea across so that they
> actually understood it.
>
> They are not "hard to follow."

For someone straightjacketed by programming a regular algorithmic language for decades, escaping to lambdas may be quite disorienting. Just tell them they'll enjoy currying. :-)

Of course, Lisp has the ultimate syntax when talking of lambda expressions. But then, as a language that can consume its own source text, it is highly elegant.

-- Paul.

On 17 Jun 2012, at 20:01, Jon Kirwan wrote:

> On Sun, 17 Jun 2012 08:40:47 +0100, you wrote:
>
>> Exceptional programming, with Ada's exceptions, looked so
>> good to a novice programmer. How bad it turned out to be.
>> Your nice, readable code turned into a mess of exception
>> handlers for things that would very rarely go wrong but
>> would take an inordinate amount of time to code for.
>
> I'm not sure why you bring in a system that makes things a
> "mess" applies to my responses, which were merely that I like
> options I can use or not use. Perhaps this is just an
> interesting side bar?
>

Exceptional programming is highly turdy IMHO; I just make an observation. You soon find your code littered with crap everywhere, and integrating a 3P library into your code that doesn't know about exceptions is a disaaaaastah daaahlink. try-catch-finally and throw specification tries to force you to deal with error handling--so you don't ignore a return code. The cure is worse than the disease in most cases.

Just $0.02 of biased opinion.

-- Paul.

On Sun, 17 Jun 2012 22:12:46 +0100, Paul wrote:

>On 17 Jun 2012, at 20:01, Jon Kirwan wrote:
>
>> On Sun, 17 Jun 2012 08:40:47 +0100, you wrote:
>>
>>> Exceptional programming, with Ada's exceptions, looked so
>>> good to a novice programmer. How bad it turned out to be.
>>> Your nice, readable code turned into a mess of exception
>>> handlers for things that would very rarely go wrong but
>>> would take an inordinate amount of time to code for.
>>
>> I'm not sure why you bring in a system that makes things a
>> "mess" applies to my responses, which were merely that I like
>> options I can use or not use. Perhaps this is just an
>> interesting side bar?
>> Exceptional programming is highly turdy IMHO; I just make an
> observation. You soon find your code littered with crap
> everywhere, and integrating a 3P library into your code that
> doesn't know about exceptions is a disaaaaastah daaahlink.
> try-catch-finally and throw specification tries to force you
> to deal with error handling--so you don't ignore a return
> code. The cure is worse than the disease in most cases.
>
> Just $0.02 of biased opinion.
>
>-- Paul.

Okay. I have used exceptions sparingly. One place I found
value that I remember right now is with a simple parser used
by a serial port command/query feature. The exception
handling made the code focus on the main thrust (simple,
easy, straightforward) and to handle invalid issues using
exceptions rather than the excessive use of status values for
function returns and all the associated garbage related to
surrounding conditional code -- it would be almost impossible
to see the main thrust through all the noise if I'd gone that
direction.

In any case, I don't have the problems you are talking about.
If I did, I wouldn't do it.

Jon
On 17/06/2012 23:00, Paul Curtis wrote:
>
> On 17 Jun 2012, at 21:09, Jon Kirwan wrote:
>
>> On Sun, 17 Jun 2012 18:10:26 +0200, David wrote:
>>
>>> On 17/06/12 02:00, Jon Kirwan wrote:
>>>> On Sat, 16 Jun 2012 23:11:29 +0200, you wrote:
>>>>
>>>>> I am not sure if noexcept will negate all the bad points
>>>>> about exceptions
>>>>
>>>> I never speak in absolutes -- except when saying that I
>>>> absolutely don't do so. :)
>>>>
>>>
>>> And I /always/ speak in absolutes - well, most of the time :-)
>>
>> Oh, cripes. I've been using iterator concepts and lazy evaluation
>> for decades with good results. These are subsets of lambda
>> calculus, as I'm learning more now.
>
> Are you late to lambda calculus? Surely not. :-) lambda
> expressions are bread and butter to a Lisp programmer.
>
> If you like thinking lambdas, you might like to get hold of a copy of
> this:
>
> This is quite old, but it does a good job and expands the mind.
> Might be a bit out of date these days, as the comment says Mine is
> pristine. :-)
>
>> But it is a VERY POWERFUL concept. One I've been using for almost
>> two decades already because they work so well and improve the
>> quality of the resulting code. If you are interested in seeing a
>> good example, I'd be happy to show you how why they helped me
>> recently and allow you to consider the alternative options to see
>> why this is the better way to handle what I faced.
>>
>> And they are NOT AT ALL hard to follow!! The C++11 syntax is the
>> ugliest, most vile way of specifying them I can imagine. It's
>> despicable. But that is syntax, not semantics. Semantically, they
>> are a thing of beauty and simplicity itself. Anyone can get the
>> idea. Anyone. I just spent a few days doing a code review to
>> programmers who'd never been so much as even exposed to the
>> concept, let alone the syntax. And they came away wondering out
>> loud why they'd never bothered to learn about it before.
>>
>> It took me 5 minutes to get the idea across so that they actually
>> understood it.
>>
>> They are not "hard to follow."
>

I am very familiar with these concepts - they were a major part of my
university degree (I studied maths and computation - not computing or
programming), although I am a little out of practice.

When working with Python, lambda functions, iterators (and lazy
evaluation), currying, mapping, list comprehension, etc., are all very
useful concepts that lead to neat and clear source code.

But in C or C++, it is ugly - as you say. Iterators are common in C++
for STL code - and they are absolutely hideous. The biggest improvement
of C++11 is the "auto" keyword that lets you get rid of half the
template type monstrosities in STL iterator code, but it is still ugly.

I agree entirely that the semantics of lambdas and other functional
programming concepts can be very nice (and the same principle applies to
other concepts, such as coroutines). But when the syntax is a mess, and
the implementation is often bigger and slower than "traditional"
programming, it's hard to see it as the right solution.

For a brief example, supposing you have a string "s" of characters, and
you want to print out the ascii codes in hex. In python, an obvious
solution is:

print ", ".join(["0x%02x" % ord(c) for c in s])

It is clear, neat and reasonably efficient in Python. But in C or C++,
it would be a terrible way to do the job involving two arbitrary lists
(meaning element nodes with links, and dynamic memory), string as class
objects with complex methods, general formatting routines (of "printf"
style), etc. A "traditional" algorithm using a loop would be much
smaller, faster and clearer in C or C++.
I am sure there /are/ times when lambdas give a clearer and better
program in C or C++. As I said, I haven't come across them in embedded
programming - but that does not mean that such situations don't exist.
And like you, if I come across such a situation I would look at the
balance between the benefits of making better code by using an unusual
(for this field) technique, and the disadvantages of using something
unfamiliar to other programmers.
> For someone straightjacketed by programming a regular algorithmic
> language for decades, escaping to lambdas may be quite disorienting.
> Just tell them they'll enjoy currying. :-)
>
> Of course, Lisp has the ultimate syntax when talking of lambda
> expressions. But then, as a language that can consume its own source
> text, it is highly elegant.
>

The great thing about Lisp coding is how happy programmers are when they
reach the end of their code :-))))))))))))))))))))))))))

On Mon, Jun 18, 2012 at 1:46 AM, David Brown wrote:

> ...
> The great thing about Lisp coding is how happy programmers are when they
> reach the end of their code :-))))))))))))))))))))))))))
>
And your Monday quiz is: Why do the parentheses all pile up on the right in
Lisp, less so in Scheme? :-)

Mike



The 2024 Embedded Online Conference