Contents of an exception object

[Ike Naar]

It's relevant to C because C makes it very obvious that you're bit-shuffling.

You seem to use word "shuffling" in an unconventional way. Usually,
"shuffling" is used to mean "changing the order of objects", without
changing the objects themselves. Like, when one shuffles a deck of
cards, the order of the cards changes, but the cards themselves
don't. When you shuffle, the cards change.

Because C makes it easy to access the actual binary bits,

Binary bits, for sure

it's clear how a C function can be rewritten in terms of shuffling
rather than higher-level concepts.

Not sure what you're saying here.
Can you give a simple example of a C function that can be rewritten in
terms of shuffling rather than higher-level concepts, and what such a
rewrite would look like?

Also because C makes asking for memory explicit. It's obvious that a
correctly-specified and written and called bit shuffling function can only
fail if it runs out of memory. If it's passed an arrangement of bits it can't
deal with (e.g. wild pointers), it's a programming error by caller, if it
executes an illegal operation on a valid input bitset, it's an internal
programming error. But it can always run out of memory, that's a sort of
inherent problem in specifying a function in terms of expected output state
given an input state.

If a program does not allocate dynamic memory and does not call
recursive functions, an upper limit for the required amount of
memory can be determined, with some effort, at compile time. If
such a program is started with a sufficient amount of memory it
can be guaranteed not to run out of memory during its lifetime.
In parts of the embedded world it is common practice to design
programs this way. It would't even matter if such a program performs
I/O, or if such a program is bit-shuffling (for whatever that
means).

In C, it's obvious what's happened, because malloc()
returns null. In other languages, the same underlying problem will happen,
but it's harder for the programmer to see.
Then the whole idea is ago separate out the bit-shuffling functions for the
IO procedures.

Sorry, can't parse that. Can you explain?

C makes that easy. If you don't include stdio.h or any third party
IO-headers, you're bit shuffling.

Elsethread you've said that functions that perform I/O also shuffle
bits. Can we conclude that *all* functions (that is, functions that
perform I/O *and* functions that don't perform I/O) shuffle bits?
If so, "bit shuffling" is a meaningless phrase.
Or is there a subtle distinction between a function that shuffles
bits and a bit shuffling function?

And since bit-shufling functions can be
idempotent, normally you won't need any third party headers anyway, So
you can see at a glance that the method has been applied.

A function f is said to be idempotent if, for all input x, f(f(x)) = f(x).
For instance, trunc() from <math.h> is such a function.
Apparently you have a different definition of idempotence in mind.
Can you clarify?

 

[Keith Thompson]

You seem to use word "shuffling" in an unconventional way. Usually,
"shuffling" is used to mean "changing the order of objects", without
changing the objects themselves. Like, when one shuffles a deck of
cards, the order of the cards changes, but the cards themselves
don't. When you shuffle, the cards change.

Perhaps "bit-twiddling" or "bit manipulation" would be more accurate.
(Though in most cases, what's being manipulated is more clearly
understood as values rather than bits.)

 

[Malcolm McLean]

You seem to use word "shuffling" in an unconventional way. Usually,
"shuffling" is used to mean "changing the order of objects", without
changing the objects themselves. Like, when one shuffles a deck of
cards, the order of the cards changes, but the cards themselves
don't. When you shuffle, the cards change.

That's true. Shuffling would imply that the total count of set and unset bits doesn't change,
which obviously isn't the case. However you don't necessarily get one output set of bits given an
input set of bits, it's better to think of it in terms of a bit set changing state.

Not sure what you're saying here.
Can you give a simple example of a C function that can be rewritten in
terms of shuffling rather than higher-level concepts, and what such a
rewrite would look like?

double add(double a, double b)
{
return a + b;
}

void bitleveladd(unsigned char *a, unsigned char *b, unsigned char *out)
{
int signa = a[0] & 0x80;
int signb = b[0] & 0x80;


...

etc. You know how floating point addition can be implemented in software.
}

If a program does not allocate dynamic memory and does not call
recursive functions, an upper limit for the required amount of
memory can be determined, with some effort, at compile time. If
such a program is started with a sufficient amount of memory it
can be guaranteed not to run out of memory during its lifetime.

In parts of the embedded world it is common practice to design
programs this way. It would't even matter if such a program performs
I/O, or if such a program is bit-shuffling (for whatever that
means).

yes, you can write individual bit-shuffling functions that use known amounts
of memory. But you can't write a general bit-shuffling function without
access to arbitrary memory.

Sorry, can't parse that. Can you explain?

It should be "from". Put your bit shuffling function in one source file, your
IO procedures in another. That's the heart of the method.

Elsethread you've said that functions that perform I/O also shuffle
bits. Can we conclude that *all* functions (that is, functions that
perform I/O *and* functions that don't perform I/O) shuffle bits?
If so, "bit shuffling" is a meaningless phrase.

It means "purely bit shuffling".
Also whilst IO procedures do shuffle bits, a good IO procedure will usually
do so in a trivial way.

Or is there a subtle distinction between a function that shuffles
bits and a bit shuffling function?

Yes. A bit-shufflign functions does nothing else. And typically it shuffles bits
in a very non-trivial way, e.g. output is the shortest route between N cities on
the Cartesian plane.

A function f is said to be idempotent if, for all input x, f(f(x)) = f(x).
For instance, trunc() from <math.h> is such a function.
Apparently you have a different definition of idempotence in mind.
Can you clarify?

That's a mathematical definition, which unfortunately uses the same word.
In programming, something which is idempotent doesn't depend on anything
else. It doesn't call any subroutines or use any definitions it doesn't
itself supply.

 

[David Brown]

That's a mathematical definition, which unfortunately uses the same word.

That's a slightly odd way to put it. It gives the impression that the
mathematicians took the word from the computer scientists and gave it a
new meaning!

In programming, something which is idempotent doesn't depend on anything
else. It doesn't call any subroutines or use any definitions it doesn't
itself supply.

That is close, but wrong. In computer science (excluding function
programming languages, which tend to follow the mathematical meaning
closer), an "idempotent function" is one which will give the same result
each time you call it with the same input values. Side-effects are
therefore limited, but not impossible, it can call other functions as
long as they too are idempotent, and it can access any external global
data as long as it does not affect the result.

For example, this function is idempotent (baring any race conditions
that I might have overseen - it is just a simple example):

double cachedSine(double x) {
static bool cacheValid = false;
static double lastX;
static double lastY;

if (cacheValid && (x == lastX)) {
return lastY;
}
lastX = x;
lastY = sin(x);
cacheValid = true;
return lastY;
}

This calls other functions (sin), writes to static data, and obviously
uses "definitions it doesn't itself supply". A more complex example
could store the cached values in another module, on a file on disk (as
long as that file is private to the function), etc.

To be idempotent, all that is needed is that every time the function is
called with the same inputs, you get the same observable result. A
compiler can therefore omit calls to the function if it already knows
the results from previous calls.

 

[Ben Bacarisse]

It should be "from".

(... and the "ago" should be "to")

Put your bit shuffling function in one source file, your
IO procedures in another. That's the heart of the method.

I prefer to organise programs by component, so I won't be doing this.
Sometimes the program's IO is a separate component, but I don't want to
move get_random_bits() from random.c to io.c just because it reads
/dev/random.

And what kind of function is this:

void map(double (*f)(double), double a[], size_t n)
{
for (size_t i = 0; i < n; i++)
a = f(a);
}

A call like map(sqrt, x, 42); would seem to be "bit-shuffling", but call
it like this:

double print(double x) { printf("%f\n", x); return x; }
...
map(print, x, 3);

and it's pure IO.

That's a mathematical definition, which unfortunately uses the same
word.

Yes, it's been used this way for more than a century and the uses in
computing, that I know of, comport with this meaning. The OED includes
the usual computing use (with a quote from a 2003).

In programming, something which is idempotent doesn't depend on anything
else. It doesn't call any subroutines or use any definitions it doesn't
itself supply.

Did you just make that up, or do you have a reference for this usage?
You have a history of just making stuff up here, so I'd like some sort
of evidence before updating my usage.

If you are right, I think it is a shame. "Self-contained" seems to be
perfectly adequate for your meaning, but what on earth will we use for
the very useful concept that was once idempotency?

 

[Keith Thompson]

That's a mathematical definition, which unfortunately uses the same word.
In programming, something which is idempotent doesn't depend on anything
else. It doesn't call any subroutines or use any definitions it doesn't
itself supply.

My understanding is that the word "idempotent" has essentially the
same meaning in programming that it has in mathematics, and it's
the meaning Ike describes, not the one you describe.

This article: <http://en.wikipedia.org/wiki/Idempotence> supports
Ike's position (and mine), and flatly contradicts yours.

Can you cite a source that supports your usage of the word
"idempotent"? If not, I ask you to be more careful in your use
of technical terms, and less eager to invent your own meanings for
words that already have established meanings. Any valid technical
points you're trying to make are being obscured by the repeated
and ongoing arguments about what words mean.

 

[Malcolm McLean]

Can you cite a source that supports your usage of the word
"idempotent"? If not, I ask you to be more careful in your use
of technical terms, and less eager to invent your own meanings for
words that already have established meanings. Any valid technical
points you're trying to make are being obscured by the repeated
and ongoing arguments about what words mean.

I've heard the word used in that sense.

But looking it up it seems it's an incorrect usage.

 

[James Kuyper]

My understanding is that the word "idempotent" has essentially the
same meaning in programming that it has in mathematics, and it's
the meaning Ike describes, not the one you describe.

This article: <http://en.wikipedia.org/wiki/Idempotence> supports
Ike's position (and mine), and flatly contradicts yours.

That page says:
| In computer science, the term idempotent is used more comprehensively
| to describe an operation that will produce the same results if
| executed once or multiple times.

In other words, f(x) == f(x), which is a very different statement from
f(f(x)) == f(x). Having the value of f(x) not depend upon anything other
than x itself is an idea related to the one that Malcolm describes. The
second part of his definition, on the other hand, has nothing to do with
either the mathematical or computer science definitions of "idempotent".

 

[Keith Thompson]

Quick summary: Never mind, I was mistaken.

My understanding is that the word "idempotent" has essentially the
same meaning in programming that it has in mathematics, and it's
the meaning Ike describes, not the one you describe.

This article: <http://en.wikipedia.org/wiki/Idempotence> supports
Ike's position (and mine), and flatly contradicts yours.

Can you cite a source that supports your usage of the word
"idempotent"? If not, I ask you to be more careful in your use
of technical terms, and less eager to invent your own meanings for
words that already have established meanings. Any valid technical
points you're trying to make are being obscured by the repeated
and ongoing arguments about what words mean.

My previous post is incorrect, and I apologize for the error.
I did not read the Wikipedia article closely enough. In fact,
it does support a meaning for "idempotent" that's close (but not
identical) to the way Malcolm uses the term.

Quoting from the article:

In computer science, the term idempotent is used more
comprehensively to describe an operation that will produce the
same results if executed once or multiple times. This may have
a different meaning depending on the context in which it is
applied. In the case of methods or subroutine calls with side
effects, for instance, it means that the modified state remains
the same after the first call. In functional programming,
though, an idempotent function is one that has the property
f(f(x)) = f(x) for any value x.

I was familiar with the mathematical meaning of the term, and the
similar meaning used in functional programming, and I incorrectly
assumed that the same meaning applied to programming in general.
This is the first time I've encountered the usage of "idempotent" to
refer to a function that merely returns the same result for the same
argument, rather than one with the property that f(f(x)) == f(x).

I agree with Malcolm that it's unfortunate that the term is used
inconsistently.

(Malcolm's definition still doesn't quite match the meaning mentioned
by the Wikipedia article; a function that depends on other things
can still be idempotent.)

 

[Ben Bacarisse]

Quick summary: Never mind, I was mistaken.

Quoting from the article:

In computer science, the term idempotent is used more
comprehensively to describe an operation that will produce the
same results if executed once or multiple times. This may have
a different meaning depending on the context in which it is
applied. In the case of methods or subroutine calls with side
effects, for instance, it means that the modified state remains
the same after the first call. In functional programming,
though, an idempotent function is one that has the property
f(f(x)) = f(x) for any value x.

(Malcolm's definition still doesn't quite match the meaning mentioned
by the Wikipedia article; a function that depends on other things
can still be idempotent.)

I don't see why you say "not quite". His (invented?) meaning seems to
be all about dependencies[1] and not at all about effects. There are
idempotent function that are not MM-idempotent, and MM-idempotent
function that are not idempotent.

[1] The wording seems ambiguous to me. Is it "doesn't (call any
subroutines or use any definitions) it doesn't itself supply", or is it
"doesn't (call any subroutines) or (use any definitions it doesn't
itself supply)"?

 

[Malcolm McLean]

I don't see why you say "not quite". His (invented?) meaning seems to
be all about dependencies[1] and not at all about effects. There are
idempotent function that are not MM-idempotent, and MM-idempotent
function that are not idempotent.

It seems I've picked up on a slightly wrong use of the word.

But it's easy to see how it happened.

double foo(double theta)
{
return sin(theta);
}

will return slightly different values depending which maths library you link in.

double foo(double theta)
{
int shriek = 1;
double num = 1.0;
double answer = 0;

for(i=1;i<=7;i++)
{
shriek *= i;
num *= theta;
if(i % 2)
answer += num/shriek * ((i % 4) == 1 ? 1 : -1);
}
return answer;

}

always returns the same value given the same floating point unit.

 

[Stefan Ram]

That page says:
|In computer science, the term idempotent is used more comprehensively
|to describe an operation that will produce the same results if
|executed once or multiple times.
In other words, f(x) == f(x)

This is obviously not a rewording of the quotation »in other words«!

The quotation is more vague than »f(x) == f(x)«. So, »f(x) == f(x)«
is an interpretation. It is not what usually is intended by »idempotent«.

The quotation is too vague to be used in a programming language context;
as you have shown, it can be misleading.

The quotation can be interpreted to be more in conformance with the
usual meaning: An »operation« is not a C function! An operation acts
on a state! So think of lines of assembler code with opcodes: If

OP0

has the same functional¹ behavior as

OP0
OP0

, then OP0 is idempotent.

This is translated to f(state)=f(f(state)), when the state is explicitly
passed as an argument.

¹ http://en.wikipedia.org/wiki/Functional_requirement

 

[Jorgen Grahn]

"The latter"?

You can get an effect that suits your purposes, but IMO it won't be
similar to exceptions.

Can do that.
How?


Can do that too!

How? I cannot see how that would be possible without language support,
or very intrusive changes to all code which might be "unwound" by an
exception.

....

Thanks, no, I hadn't considered calling abort() ... for at least three
reasons:

1. I didn't know about it.
2. I have a simple, if verbose, way to do what I want to do.

3. This is for bare-metal code. There is no C run-time module, no OS, no
signalling, etc.

Ok, I don't think you mentioned that before. Then you would have to
implement abort() yourself -- it could write a register/stack trace to
flash or whatever, and then blink a LED forever, or start a debugger,
or whatever your machine can offer.

/Jorgen

 

[James Kuyper]

You can get an effect that suits your purposes, but IMO it won't be
similar to exceptions.

"The latter" implies that two options have been provided, and specifies
selection of the second option; "The former" is how you would identify
selection of the first option. I don't recognize an option (two-valued
or otherwise) having been provided. Perhaps it would help if you could
identify the two options that "The former" and "The latter" would refer to?

 

[Kaz Kylheku]

My understanding is that the word "idempotent" has essentially the
same meaning in programming that it has in mathematics, and it's
the meaning Ike describes, not the one you describe.

My understanding is that the meaning of "idempotent" in programming has to do
with something that is irrelevant in "run of the mill" mathematics: namely,
characterizing certain *state mutating* operations. Idempotent operations can
be done two or more times, with the same external effect as if they were done
once:

- multiple writes of the same data to the same spot in memory or in a file
- interning a Lisp symbol

Idempotent operations are useful in networking, in the face of
packet retransmission.

For instance, if a file write operation is turned into a remote
procedure call, if the packet is repeated, then the write could happen
twice. If the write operation advances the file pointer, then the
server has to take steps to squash duplicate operations.

But if the write operation is idempotent (carries the absolute location of the
write) then there is little harm in just doing it as many times as it was
received. (Of course, the file modification timestamp will be that of the most
recent write, that is all.)

The algebraic sense of idempotent is relevant in computing too. A compiler
doesn't have to worry about having applied some operation to a parse tree too
many times if it is idempotent.

If we are generating code with Lisp macro, we know that extra levels of progn
will not change the result: (progn (progn (progn e1 e2))) is the same as (progn
e1 e2). We can let the optimizer deal with it.

In C, casts are idempotent: (int) (int) doesn't do anything more than (int).
Extra parentheses around an expression are idempotent, etc.

This article: <http://en.wikipedia.org/wiki/Idempotence> supports

Ike's position (and mine), and flatly contradicts yours.

Can you cite a source that supports your usage of the word
"idempotent"?

It doesn't even follow from the Latin roots.

 

[Kaz Kylheku]

You seem to use word "shuffling" in an unconventional way. Usually,
"shuffling" is used to mean "changing the order of objects", without
changing the objects themselves. Like, when one shuffles a deck of
cards, the order of the cards changes, but the cards themselves
don't. When you shuffle, the cards change.

That's true. Shuffling would imply that the total count of set and unset bits doesn't change,
which obviously isn't the case. However you don't necessarily get one output set of bits given an
input set of bits, it's better to think of it in terms of a bit set changing state.

Not sure what you're saying here.
Can you give a simple example of a C function that can be rewritten in
terms of shuffling rather than higher-level concepts, and what such a
rewrite would look like?

double add(double a, double b)
{
return a + b;
}

void bitleveladd(unsigned char *a, unsigned char *b, unsigned char *out)
{
int signa = a[0] & 0x80;
int signb = b[0] & 0x80;


...

etc. You know how floating point addition can be implemented in software.
}

If a program does not allocate dynamic memory and does not call
recursive functions, an upper limit for the required amount of
memory can be determined, with some effort, at compile time. If
such a program is started with a sufficient amount of memory it
can be guaranteed not to run out of memory during its lifetime.

In parts of the embedded world it is common practice to design
programs this way. It would't even matter if such a program performs
I/O, or if such a program is bit-shuffling (for whatever that
means).

yes, you can write individual bit-shuffling functions that use known amounts
of memory. But you can't write a general bit-shuffling function without
access to arbitrary memory.

Sorry, can't parse that. Can you explain?

It should be "from". Put your bit shuffling function in one source file, your
IO procedures in another. That's the heart of the method.

Elsethread you've said that functions that perform I/O also shuffle
bits. Can we conclude that *all* functions (that is, functions that
perform I/O *and* functions that don't perform I/O) shuffle bits?
If so, "bit shuffling" is a meaningless phrase.

It means "purely bit shuffling".
Also whilst IO procedures do shuffle bits, a good IO procedure will usually
do so in a trivial way.

Or is there a subtle distinction between a function that shuffles
bits and a bit shuffling function?

Yes. A bit-shufflign functions does nothing else. And typically it shuffles bits
in a very non-trivial way, e.g. output is the shortest route between N cities on
the Cartesian plane.

A function f is said to be idempotent if, for all input x, f(f(x)) = f(x).
For instance, trunc() from <math.h> is such a function.
Apparently you have a different definition of idempotence in mind.
Can you clarify?

That's a mathematical definition, which unfortunately uses the same word.
In programming, something which is idempotent doesn't depend on anything
else. It doesn't call any subroutines or use any definitions it doesn't
itself supply.

There is a perfectly good Latin-derived word for "doesn't depend on anything
else", namely:

independent

Doh?

Idempotent, which sounds vaguely similar, has these Latin roots:

- potentia (power, force)

- idem (same, the very same)

The combination refers to that redundant applications do the same thing;
that is to say, higher powers (potentiae) of the operation are the same (idem)
as just one:
2
For instance, the second power of abs, abs (x) is the same as the first,
abs(x).

 

[Kenny McCormack]

My understanding is that the word "idempotent" has essentially the
same meaning in programming that it has in mathematics, and it's
the meaning Ike describes, not the one you describe.

This article: <http://en.wikipedia.org/wiki/Idempotence> supports
Ike's position (and mine), and flatly contradicts yours.

Can you cite a source that supports your usage of the word
"idempotent"? If not, I ask you to be more careful in your use
of technical terms, and less eager to invent your own meanings for
words that already have established meanings. Any valid technical
points you're trying to make are being obscured by the repeated
and ongoing arguments about what words mean.

Kiki, old friend, I have a suggestion for you.

Why don't you just killfile Malcolm and be done with it?
It'll do your blood pressure much good.

--
The problem in US politics today is that it is no longer a Right/Left
thing, or a Conservative/Liberal thing, or even a Republican/Democrat
thing, but rather an Insane/not-Insane thing.

(And no, there's no way you can spin this into any confusion about
who's who...)

 

[Ben Bacarisse]

I don't see why you say "not quite". His (invented?) meaning seems to
be all about dependencies[1] and not at all about effects. There are
idempotent function that are not MM-idempotent, and MM-idempotent
function that are not idempotent.

It seems I've picked up on a slightly wrong use of the word.

But it's easy to see how it happened.

double foo(double theta)
{
return sin(theta);
}

will return slightly different values depending which maths library you link in.

double foo(double theta)
{
int shriek = 1;
double num = 1.0;
double answer = 0;

for(i=1;i<=7;i++) for(int i=1;i<=7;i++)
{
shriek *= i;
num *= theta;
if(i % 2)
answer += num/shriek * ((i % 4) == 1 ? 1 : -1);
}
return answer;

}

always returns the same value given the same floating point unit.

This is another artificial distinction. (I accept that may be what
confused you, but it's still a made-up distinction.) If sin is
implemented in hardware, both functions always return the same result on
the same FP unit. And if FP arithmetic is implemented on software, the
second one also depends on the math library you link in.

You have to assume hardware arithmetic in the one case, and assume a
replaceable standard function in the second. Neither is justified by
the C language alone.

 

[Malcolm McLean]

This is another artificial distinction. (I accept that may be what
confused you, but it's still a made-up distinction.) If sin is
implemented in hardware, both functions always return the same result on
the same FP unit. And if FP arithmetic is implemented on software, the
second one also depends on the math library you link in.

Yes, a certain amount of looseness is introduced by the fact that
floating point arithmetic isn't exact or consistent across platforms.
Though in fact that's being tightened up.

You have to assume hardware arithmetic in the one case, and assume a
replaceable standard function in the second. Neither is justified by
the C language alone.

It doesn't matter if arithmetic is implemented in hardware or software,
just the bit pattern of the result. However you can reasonably implement
higher-level functions in several ways. When I did games programming we
commonly implemented sin() via a look-up table.

 

[Ben Bacarisse]

Malcolm McLean <[email protected]> writes:

Put your bit shuffling function in one source file, your
IO procedures in another. That's the heart of the method.

I prefer to organise programs by component, so I won't be doing this.
Sometimes the program's IO is a separate component, but I don't want to
move get_random_bits() from random.c to io.c just because it reads
/dev/random.

And what kind of function is this:

void map(double (*f)(double), double a[], size_t n)
{
for (size_t i = 0; i < n; i++)
a = f(a);
}

A call like map(sqrt, x, 42); would seem to be "bit-shuffling", but call
it like this:

double print(double x) { printf("%f\n", x); return x; }
...
map(print, x, 3);

and it's pure IO.

This seems to have been lost in the idempotentcy issue, but this bit is
about your function/procedure distinction.

<snip>